En informática , más precisamente, en la teoría de los autómatas finitos deterministas (DFA), una palabra de sincronización o secuencia de reinicio es una palabra en el alfabeto de entrada del DFA que envía cualquier estado del DFA a uno y el mismo estado. [1] Es decir, si un conjunto de copias del DFA se inicia en diferentes estados y todas las copias procesan la palabra de sincronización, todas terminarán en el mismo estado. No todos los DFA tienen una palabra de sincronización; por ejemplo, un DFA con dos estados, uno para palabras de longitud par y otro para palabras de longitud impar, nunca se puede sincronizar.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/6/69/Road_coloring_conjecture.svg/220px-Road_coloring_conjecture.svg.png)
Existencia
Dado un DFA, el problema de determinar si tiene una palabra sincronizada se puede resolver en tiempo polinomial [2] utilizando un teorema de Ján Černý. Un enfoque simple considera el conjunto de estados de potencia del DFA y crea un gráfico dirigido donde los nodos pertenecen al conjunto de potencia y un borde dirigido describe la acción de la función de transición. Una ruta desde el nodo de todos los estados a un estado singleton muestra la existencia de una palabra de sincronización. Este algoritmo es exponencial en el número de estados. Sin embargo, se obtiene un algoritmo polinomial debido a un teorema de Černý que explota la subestructura del problema y muestra que existe una palabra de sincronización si y solo si cada par de estados tiene una palabra de sincronización.
Largo
Si un DFA con estados tiene una palabra de sincronización, debe tener una longitud como máximo ?
El problema de estimar la longitud de las palabras sincronizadas tiene una larga historia y fue planteado de forma independiente por varios autores, pero se conoce comúnmente como la conjetura de Černý . En 1969, Ján Černý conjeturó que ( n - 1) 2 es el límite superior de la longitud de la palabra de sincronización más corta para cualquier DFA completo de n estados (un DFA con gráfico de transición de estado completo ). [3] Si esto es cierto, sería estricto: 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] El mejor límite superior conocido es ( n 3 - n) / 6, lejos del límite inferior. [5] Para n DFAs -state más de un k -Carta alfabeto de entrada, un algoritmo por David Eppstein encuentra una palabra de sincronización de longitud a lo sumo 11 n 3 /48 + O ( n 2 ), y se ejecuta en tiempo complejidad O ( n 3 + kn 2 ). 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 conservan el orden cíclico de los estados, describe un algoritmo diferente con el tiempo O ( kn 2 ) que siempre encuentra la palabra de sincronización más corta, prueba que estos autómatas siempre tienen una palabra de sincronización. de longitud como máximo ( n - 1) 2 (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 . [2]
Carretera para colorear
El problema colorear carretera es el problema de etiquetar los bordes de una normal gráfico dirigido con los símbolos de una k alfabeto de entrada -Carta (donde k es el grado de salida de cada vértice) con el fin de formar un DFA sincronizable. Benjamin Weiss y Roy Adler conjeturaron en 1970 que cualquier dígrafo regular aperiódico y fuertemente conectado puede ser etiquetado de esta manera; su conjetura fue probada en 2007 por Avraham Trahtman . [6] [7]
Relacionado: Semigrupos de transformación
Un semigrupo de transformación se sincroniza si contiene un elemento de rango 1, es decir, un elemento cuya imagen es de cardinalidad 1. [8] Un DFA corresponde a un semigrupo de transformación con un grupo electrógeno distinguido.
Referencias
- ^ Avraham Trakhtman: Sincronización de autómatas, algoritmos, Conjetura de Cerny . Consultado el 15 de mayo de 2010.
- ↑ a b Eppstein, David (1990), "Reset Sequences for Monotonic Automata" (PDF) , SIAM Journal on Computing , 19 (3): 500-510, doi : 10.1137 / 0219033 .
- ^ Volkov, Mikhail V. (2008), "Sincronización de autómatas y la conjetura de Černý", Proc. 2do Int'l. Conf. Teoría y aplicaciones del lenguaje y los autómatas (LATA 2008) , LNCS, 5196 , Springer-Verlag, págs. 11–27, doi : 10.1007 / 978-3-540-88282-4_4; ver en particular p. 19
- ^ Černý, Ján (1964), "Poznámka k homogénnym experimentom s konečnými automatmi" (PDF) , Matematicko-fyzikálny časopis Slovenskej Akadémie Vied , 14 : 208–216 (en eslovaco).
- ^ Alfiler, J.-E. (1983), "Sobre dos problemas combinatorios derivados de la teoría de autómatas" (PDF) , Matemáticas combinatorias (Marseille-Luminy, 1981) , North-Holland Math. Stud., 75 , Amsterdam: North-Holland, págs. 535–548, doi : 10.1016 / S0304-0208 (08) 73432-7 , MR 0841339; ver nota al final refiriéndose a la mejora por Frankl, P. (1982), "Un problema extremo para dos familias de conjuntos", European Journal of Combinatorics , 3 (2): 125-127, doi : 10.1016 / S0195-6698 (82) 80025-5 , MR 0670845
- ^ Adler, RL; Weiss, B. (1970), "Similitud de automorfismos del toro", Memorias de la American Mathematical Society , 98.
- ^ Trahtman, AN (2009), "The road coloring problem", Israel Journal of Mathematics , 172 : 51–60, arXiv : 0709.0099 , doi : 10.1007 / s11856-009-0062-5 , MR 2534238
- ^ Cameron, Peter (2013), Grupos de permutación y semigrupos de transformación (PDF).
Otras lecturas
- Rystsov, IC (2004), "Conjetura de Černý: retrospectivas y perspectivas", Proc. Worksh. Sincronización de autómatas, Turku (WSA 2004).
- Jürgensen, H. (2008), "Sincronización", Información y Computación , 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ý", Proc. 2do Int'l. Conf. Teoría y aplicaciones del lenguaje y los autómatas (LATA 2008) (PDF) , LNCS, 5196 , Springer-Verlag, págs. 11–27