Conjetura de Černý
En 1964 Jan Černý propuso que dado un AFD (Autómata finito determinista) sincronizable de
.Este problema es uno de los más antiguos y famosos junto con Teorema del coloreo de carreteras en la teoría de Autómatas Finitos.
Por otro lado, se ha visto que una cota superior en la longitud de la palabra de reinicio es de tamaño cúbico en
El problema de la sincronización de un AFD arriba naturalmente, pues la sincronización hace que el comportamiento de un autómata sea "resistente" a errores de ingreso de órdenes dado que, después de la detección de un error, una palabra de sincronización puede reiniciar el autómata a su estado original, como si no hubiera ocurrido ningún error.
Un problema con una larga historia es el de la estimación de la longitud mínima de una palabra de sincronización para un AFD completo.Mejor conocido ahora como una conjetura de Černý, este problema fue propuesto independientemente por otros autores también.
Jan Černý en 1964 encontró un AFD completo de
para un alfabeto de tamaño
Este problema puede ser reducido a autómatas con un grafo asociado fuertemente conexo.
un AFD con conjunto de entradas
es denominada una palabra de reinicio para
si esta palabra envía todos los estados de
a un único estado, esto es
Un autómata que admite una palabra de reinicio se dice sincronizable.
Un autómata sincronizable de
Inicialmente las cotas superiores encontradas para la longitud de las palabras de sincronización no alcanzaban a ser polinomiales; la más conocida de las cotas superiores ahora es
No hay ejemplos de autómatas tales que la longitud de la menor palabra de sincronización sea mayor que
más aún, los ejemplos de autómatas con palabra de sincronización cuya longitud sea
[3] Una manera natural de ver la conjetura de Černý desde un punto de vista probabilístico lleva a una forma de proponer la conjetura de Černý desde las siguientes preguntas: Entendiéndose en estas preguntas que al referirse a alta probabilidad significa"con probabilidad que tiende a
va al infinito"[4] Dado
, AFD aleatorio de
, hay una probabilidad de
de que sea sincronizable, para
el rango de convergencia es bastante estrecho.
entonces, es casi seguro que
[5] Dándose así una respuesta afirmativa a la primera pregunta.
estados en un alfabeto de al menos dos letras
se tiene que, para cualquier
estados, tenga una palabra de sincronización de tamaño menor que
tiende a infinito.
[6] Dándose así respuesta afirmativa a la segunda pregunta.
