A carregar...
Publicação
The word problem for omega-terms over DA
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 280.38 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
In this paper, we solve the word problem for ω-terms over DA. We extend to DA the ideas used by Almeida and Zeitoun to solve the analogous problem for the pseudovariety R applying also a representation by automata of implicit operations on DA, which was recently obtained by the author. Considering certain types of factors of an implicit operation on DA, we can prove that a pseudoword on DA is an ω-term if and only if the associated minimal DA- automaton is finite. Finally, we complete the result by effectively computing in polynomial time the minimal DA-automaton associated to an ω-term.
Descrição
Palavras-chave
Finite monoid Pseudovariety Word problem Pseudoword Omega-term Aperiodic Regular D-class
Contexto Educativo
Citação
Editora
Elsevier