Palavra de sincronia
# Palavra de sincronia

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. 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)$^2$ é 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). 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$^3$- n)/6, bem distante do limitante inferior. 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$^3$/48 + O(n$^2$), que roda em complexidade de tempo O(n$^3$+kn$^2$). 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$^2$) 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)$^2$ (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)$^2$.
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.