• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2013.tde-28082013-101244
Documento
Autor
Nome completo
Leticia Gindri
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2013
Orientador
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.
dissertacao.pdf (909.62 Kbytes)
Data de Publicação
2013-09-05
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2020. Todos os direitos reservados.