En informática , más precisamente, en la teoría de autómatas finitos deterministas (DFA), la palabra de sincronización (o secuencia de contracción ) en el alfabeto de entrada del autómata asigna todos sus estados al mismo estado [1] . Es decir, si una palabra parte del conjunto de todos los estados del autómata, pasando por todos los arcos orientados con la misma velocidad, todos los caminos terminarán simultáneamente en el mismo estado. No todos los DFA tienen una palabra de sincronización, por ejemplo, un DFA con dos estados y ciclos de dos longitudes nunca se puede sincronizar.
El problema de estimar la longitud de una palabra sincronizada tiene una larga historia y ha sido planteado de forma independiente por varios autores, pero se ha vuelto ampliamente conocido como la conjetura de Cherny. En 1964, Jan Czerny [1] sugirió que (N - 1) 2 es un límite superior pronunciado en la longitud de la palabra de sincronización más corta para cualquier DFA con N estados y K bordes salientes multicolores desde cada vértice (un DFA con un gráfico de transición completo). Cerny, allá por 1964, encontró una clase de autómatas (con el número N de estados para cualquier N natural) cuya palabra de sincronización más corta tiene esta longitud. El límite superior más conocido para esta longitud hoy en día es (N 3 - N) / 6 y está lejos del límite inferior.
Para un DFA de estado N sobre un alfabeto de K caracteres, el algoritmo de David Epstein encuentra la palabra de sincronización en O (N 3 + n 2 k) tiempo y O (n 2 ) [2] espacio de memoria . Este documento también prueba la integridad NP de encontrar una palabra de sincronización de longitud mínima.
El problema de coloreado de caminos es el problema de colorear los bordes de un gráfico dirigido regular con los símbolos (colores) de un alfabeto de entrada de K símbolos (donde K es también el grado exterior de cada vértice) para formar un DFA sincronizado. Benjamin Weiss y Roy Adler conjeturaron en 1970 que cualquier dígrafo fuertemente conectado con un grado exterior constante de cada vértice y un máximo común divisor de las longitudes de todos los ciclos igual a uno tiene una coloración sincronizada [3] . Su conjetura fue probada en 2007 por Abram Trakhtman [4] .