Em ciência da computação, mais precisamente, na teoria de autômato finito determinístico (AFD), uma palavra sincronizadora ou sequência de recomeço é uma palavra do alfabeto de entrada da AFD que envia qualquer estado da AFD para o mesmo e único estado.^[1] Isto é, se um conjunto de cópias de uma AFD são iniciadas em diferentes estados, e todas as cópias processam a palavra sincronizadora na mesma velocidade, elas irão no final alcançar o mesmo estado uma das outras, ao mesmo tempo. Nem toda AFD possui uma palavra sincronizadora; por exemplo, uma AFD com dois estados, um para palavras de tamanho par e outro para palavras de tamanho ímpar, jamais pode ser sincronizado.

O problema de estimar o tamanho de palavras sincronizadoras possui uma longa história e vários autores propuseram-no independentemente, mas é comumente conhecido como a Conjectura de Černý . Em 1964 Jan Černý conjecturou que (n − 1)² é o limitante superior para o comprimento da palavra sincronizadora mais curta para qualquer AFD completa de n estados (uma AFD com grafo de transição de estados completo).^[1][2] Se isso for verdade, seria ótimo: em um paper de 1964, Černý descreve uma classe de autômatos (indexados por seu número n de estados) para a qual as menores palavras sincronizadora possuem esse tamanho. O melhor limitante superior conhecido é (n ³ - n)/6, bem distante do limitante inferior.^[3] Para AFDs de n estados sob um alfabeto de entrada de k símbolos, um algoritmo de David Eppstein encontrou uma palavra sincronizadora de tamanho no máximo 11n³/48 + O(n²), que roda em complexidade de tempo O(n³+kn²). Este algoritmo nem sempre encontra a menor palavra sincronizadora possível para um dado autômato; como Eppstein também demonstra, o problema de achar a menor palavra sincronizadora é NP-completo. Entretanto, para uma classe especial de autômatos em que todas as transições de estados preservam a ordem cíclica dos estados, ele descreve um algoritmo diferente com tempo O(kn²) que sempre encontra a palavra sincronizadora mais curta, além de provar que tais autômatos necessariamente possuem uma palavra sincronizadora de tamanho máximo (n − 1)² (o limite descrito pela conjectura de Černý), e exibe exemplos de autômatos com esse formato particular cujas palavras sincronizadora tem comprimento exato (n − 1)².^[4]

O problema da coloração de grafos é o problema de rotular cada aresta de um grafo regular dirigido com os símbolos de um alfabeto de tamanho k (em que k é o grau de saída de cada vértice) com o objetivo de formar uma AFD sincronizável. Foi conjecturado em 1970 por Benjamin Weiss e Roy Adler que qualquer digrafo fortemente conectado, aperiódico e regular pode ser rotulado dessa forma; a conjectura foi provada em 2007 por Avraham Trahtman.^[5][6]

• Rystsov, I. C. (2004), «Proc. Worksh. Synchronizing Automata, Turku (WSA 2004)», Černý's conjecture: retrospects and prospects .
• Jürgensen, Helmut (1 de setembro de 2008). «Synchronization». Information and Computation. 206 (9–10): 1033-1044. doi:10.1016/j.ic.2008.03.005 
• Volkov, Mikhail V. (2008), «Cópia arquivada» (PDF), Springer-Verlag, Synchronizing Automata and the Černý Conjecture, LNCS, 5196, pp. 11–27, consultado em 8 de julho de 2015, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗