Palavra de sincronia

Origem: Wikipédia, a enciclopédia livre.
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.[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)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).[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 3 - 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 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.[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]

Referências[editar | editar código-fonte]

  1. ↑ a b Avraham Trakhtman: Synchronizing automata, algorithms, Cerny Conjecture. Accessed May 15, 2010.
  2. ↑ Černý, J. (1964), «Poznámka k homogénnym experimentom s konečnými automatami» (PDF), Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14: 208–216  (em eslovaco).
  3. ↑ 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
  4. ↑ Eppstein, David (1990), «Reset Sequences for Monotonic Automata» (PDF), SIAM Journal on Computing, 19 (3): 500–510, doi:10.1137/0219033. 
  5. ↑ Adler, R. L.; Weiss, B. (1970), «Similarity of automorphisms of the torus», Memoires of the American Mathematical Society, 98 .
  6. ↑ Trahtman, Avraham (2007). «The road coloring problem». arXiv:0709.0099Acessível livremente .

Leitura complementar[editar | editar código-fonte]

  • 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) 🔗 
Obtida de "https://pt.wikipedia.org/w/index.php?title=Palavra_de_sincronia&oldid=66175635"