thumb|Essa gravura representa uma AFD com oito estados e dois símbolos de entrada, azul e vermelho. A palavra azul-vermelho-vermelho-azul-vermelho-vermelho-azul-vermelho-vermelho é uma palavra de sincronia que envia qualquer estado para o estado amarelo; a palavra azul-azul-vermelho-azul-azul-vermelho-azul-azul-vermelho é outra palavra de sincronia que envia qualquer estado para o estado verde. 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.Avraham Trakhtman: Synchronizing automata, algorithms, Cerny Conjecture. Accessed May 15, 2010. 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). (em eslovaco). 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.http://arxiv.org/abs/1104.2409v7 Trahtman em certo ponto pensou ter provado a existência de um melhor limite de n(7n2+6n−16)/48, mas a prova foi eventualmente mostrada como incorreta e o paper foi corrigido, deixando o melhor limite superior conhecido como (n^3 - n)/6 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 11n3/48 + O(n2), que roda em complexidade de tempo O(n3+kn2). 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(kn2) 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...
Referências
Leitura complementar .
Categoria:Teoria dos autômatos