Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2013.tde-28082013-101244
Document
Author
Full name
Leticia Gindri
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2013
Supervisor
Committee
Mandel, Arnaldo (President)
Lee, Orlando
Soares, Jose Augusto Ramos
Title in Portuguese
Autômatos sincronizados e a Conjectura de Cerný
Keywords in Portuguese
autômato sincronizado
Conjectura de Cerný
palavra sincronizadora
sincronização.
Abstract in Portuguese
Cerný, em 1964, conjecturou que um autômato sincronizado com n estados possui uma palavra sincronizadora mÃnima de tamanho no máximo (n-1)². Esta conjectura permanece em aberto. Neste trabalho são apresentados algoritmos para obter palavras sincronizadoras e é feito um experimento comparativo entre os resultados obtidos por estes algoritmos em relação a algumas séries infinitas de autômatos. Por fim, é feito um breve histórico sobre os resultados parciais obtidos até a presente data e alguns destes trabalhos são apresentados em mais detalhes.
Title in English
Synchronizing Automata and the Cerný Conjecture
Keywords in English
Cerný Conjecture
reset words
shortest reset word.
synchronizing automata
Abstract in English
Cerný, on 1964, conjectured that a synchronizing automata with n states has a synchronizing word of size at most (n-1)². The conjecture remains open. We show some algorithms for obtaining synchronizing sequences and a comparative experiment between these algorithms with respect to some infinite series of automata. Furthermore, we briefly survey some of the partial results obtained until the present day.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
dissertacao.pdf (909.62 Kbytes)
Publishing Date
2013-09-05