Una conjetura relacionada con la conjetura de Cerny: contraejemplo / solicitud de referencia

La conjetura de Cerny es la afirmación de que cualquier autómata de sincronización con $n$ estados tiene una palabra de longitud de sincronización como máximo $(n-1)^2$ . El mejor límite superior actual para la longitud de una palabra de sincronización es $O(n^3)$ . Digamos que dos estados se fusionan por una palabra si esa palabra lleva los dos estados al mismo estado. Un argumento de tipo lemma de bombeo muestra que en un autómata de sincronización, dos estados pueden fusionarse por una palabra de longitud como máximo $n^2$ . Suponga que la siguiente conjetura es cierta.

Conjetura. Cualquier subconjunto de $k$ estados contiene dos estados que pueden fusionarse por una palabra de longitud (digamos) como máximo $n^2/k$ . O, más generalmente, cualquier conjunto grande de estados contiene dos que pueden fusionarse por una palabra de longitud $o(n^2)$ .

Entonces podemos considerar la siguiente estrategia para construir una palabra de sincronización. Comenzamos con todos los $n$ estados. Según la conjetura anterior, hay una palabra corta que fusiona dos estados, y hacemos de esto el comienzo de nuestra palabra de sincronización. Podemos ejecutar el DFA con esta palabra a partir de todos los estados, y obtenemos un conjunto de como máximo $n-1$ estados finales. Repetimos esto con estos estados finales como nuestros nuevos estados de inicio. Después de repetir esto un número suficiente de veces, solo terminamos con un estado final. Claramente, dada la conjetura anterior, tendríamos un límite mejor que $O(n^3)$ para la longitud de la palabra de sincronización más corta.

Lo anterior motiva las siguientes preguntas:

1. ¿Hay contraejemplos conocidos de esta conjetura? La construcción original de Cerny (ver página 18 ) satisface el enunciado de la conjetura.
2. ¿Podría proporcionar una referencia para investigar ideas similares?

Encontré una respuesta parcial a la pregunta 2. La misma idea se discute en los últimos 10 minutos de esta conferencia .