Sincronizando palabra

En informática , más precisamente, en la teoría de autómatas finitos deterministas (AFD), una palabra de sincronización o secuencia de reinicio es una palabra en el alfabeto de entrada del AFD que envía cualquier estado del AFD a un mismo estado. ^{[ 1 ]} Es decir, si un conjunto de copias del AFD se inician cada una en estados diferentes, y todas las copias procesan la palabra de sincronización, todas terminarán en el mismo estado. No todos los AFD tienen una palabra de sincronización; por ejemplo, un AFD con dos estados, uno para palabras de longitud par y otro para palabras de longitud impar, nunca puede sincronizarse.

Dado un autómata finito determinista (AFD), el problema de determinar si posee una palabra sincronizadora puede resolverse en tiempo polinomial ^{[ 2 ]} utilizando un teorema de Ján Černý. Un enfoque simple considera el conjunto potencia de estados del AFD y construye un grafo dirigido donde los nodos pertenecen a dicho conjunto, y una arista dirigida describe la acción de la función de transición. Un camino desde el nodo de todos los estados hasta un estado singleton muestra la existencia de una palabra sincronizadora. Este algoritmo es exponencial en el número de estados. Sin embargo, se obtiene un algoritmo polinomial gracias a un teorema de Černý que aprovecha la subestructura del problema y demuestra que existe una palabra sincronizadora si y solo si cada par de estados posee una palabra sincronizadora.

Problema sin resolver en informática

Si un DFA con${\displaystyle n}$estados tiene una palabra de sincronización, debe tener una longitud como máximo${\displaystyle (n-1)^{2}}$¿

Más problemas sin resolver en informática

El problema de estimar la longitud de las palabras de sincronización tiene una larga historia y fue planteado independientemente por varios autores, pero se conoce comúnmente como la conjetura de Černý . En 1969, Ján Černý conjeturó que ( n − 1) ^² es la cota superior para la longitud de la palabra de sincronización más corta para cualquier DFA completo de n estados (un DFA con grafo de transición de estados completo ). ^{[ 3 ]} Si esto es cierto, sería ajustado: en su artículo de 1964, Černý exhibió una clase de autómatas (indexados por el número n de estados) para los cuales las palabras de reinicio más cortas tienen esta longitud. ^{[ 4 ] La} mejor cota superior conocida es 0,1654n³ , lejos de la cota inferior. ^{[ 5 ]} Para autómatas finitos deterministas (AFD) de n estados sobre un alfabeto de entrada de k letras, un algoritmo de David Eppstein encuentra una palabra de sincronización de longitud como máximo 11 n ³ /48 + O ( n ² ), y se ejecuta en una complejidad temporal de O ( n ³ + kn ² ). Este algoritmo no siempre encuentra la palabra de sincronización más corta posible para un autómata dado; como también muestra Eppstein, el problema de encontrar la palabra de sincronización más corta es NP-completo . Sin embargo, para una clase especial de autómatas en los que todas las transiciones de estado preservan el ^orden cíclico de los estados, describe un algoritmo diferente con tiempo O( kn² ) que siempre encuentra la palabra de sincronización más corta, demuestra que estos autómatas siempre tienen una palabra de sincronización de longitud como máximo ( n − 1) ^² (el límite dado en la conjetura de Černý) y exhibe ejemplos de autómatas con esta forma especial cuya palabra de sincronización más corta tiene una longitud exactamente ( n − 1) ^² . ^{[ 2 ]}        

El problema de la coloración de caminos consiste en etiquetar las aristas de un grafo dirigido regular con los símbolos de un alfabeto de entrada de k letras (donde k es el grado de salida de cada vértice) para formar un autómata finito determinista (AFD) sincronizable. En 1970, Benjamin Weiss y Roy Adler conjeturaron que cualquier digrafo regular fuertemente conexo y aperiódico puede etiquetarse de esta manera; su conjetura fue demostrada en 2007 por Avraham Trahtman . ^{[ 6 ] [ 7 ]}

Un semigrupo de transformación es sincronizado si contiene un elemento de rango 1, es decir, un elemento cuya imagen tiene cardinalidad 1. ^{[ 8 ]} Un DFA corresponde a un semigrupo de transformación con un conjunto de generadores distinguido.

• Rystsov, IC (2004), "La conjetura de Černý: retrospectivas y perspectivas", Actas del Taller sobre Autómatas Sincronizados, Turku (WSA 2004).
• Jürgensen, H. (2008), "Sincronización", Information and Computation , 206 ( 9–10 ): 1033–1044 , doi : 10.1016/j.ic.2008.03.005
• Volkov, Mikhail V. (2008), "Sincronización de autómatas y la conjetura de Černý", Actas de la 2.ª Conferencia Internacional sobre Teoría y Aplicaciones del Lenguaje y los Autómatas (LATA 2008) (PDF) , LNCS, vol.  5196, Springer-Verlag, pp. 11–27 .