Dissertação de Mestrado
Documento
Dissertação de Mestrado
Autor
Gindri, Leticia
(
)
Nome completo
Leticia Gindri
Unidade da USP
Instituto de Matemática e Estatística
Área do Conhecimento
Data de Defesa
2013-07-10
Imprenta
São Paulo, 2013
Orientador
Mandel, Arnaldo
(
)
Banca examinadora
Mandel, Arnaldo (Presidente)
Lee, Orlando
Soares, Jose Augusto Ramos
Título em português
Autômatos sincronizados e a Conjectura de Cerný
Palavras-chave em português
autômato sincronizado, Conjectura de Cerný, palavra sincronizadora, sincronização.
Resumo em português
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.
Título em inglês
Synchronizing Automata and the Cerný Conjecture
Palavras-chave em inglês
Cerný Conjecture, reset words, shortest reset word., synchronizing automata
Resumo em inglês
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.
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso: Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2013-09-05
Trabalhos decorrentes
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.