En informática , más precisamente, en la teoría de 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 un mismo estado. [1] Es decir, si un conjunto de copias del DFA se inician cada una 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 puede sincronizarse.
Dado un DFA, el problema de determinar si tiene una palabra sincronizadora se puede resolver en tiempo polinomial [2] utilizando un teorema debido a Ján Černý. Un enfoque simple considera el conjunto de potencia de estados del DFA y construye un grafo dirigido donde los nodos pertenecen al conjunto de potencia y una arista dirigida describe la acción de la función de transición. Una ruta 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, resulta un algoritmo polinomial debido a un teorema de Černý que explota la subestructura del problema y muestra que existe una palabra sincronizadora si y solo si cada par de estados tiene una palabra sincronizadora.
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) 2 es el límite superior para 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 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] El mejor límite superior conocido es 0,1654 n 3 , lejos del límite inferior. [5] Para DFAs de n estados sobre un alfabeto de entrada de k letras, un algoritmo de David Eppstein encuentra una palabra de sincronización con una longitud máxima de 11 n 3 /48 + O ( n 2 ), y se ejecuta en una complejidad temporal 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 la que todas las transiciones de estado preservan el orden cíclico de los estados, describe un algoritmo diferente con tiempo O( kn 2 ) 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) 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]
El problema de coloración de carreteras es el problema de etiquetar los bordes de un grafo regular dirigido 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 DFA sincronizable. En 1970, Benjamin Weiss y Roy Adler conjeturaron que cualquier dígrafo regular aperiódico y fuertemente conectado puede etiquetarse de esta manera; su conjetura fue demostrada en 2007 por Avraham Trahtman . [6] [7]
Un semigrupo de transformación es sincronizante 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 conjunto generador distinguido.
