The word problem for omega-terms over DA

作者：Moura A^*

来源：Theoretical Computer Science, 2011, 412(46): 6556-6569.

DOI：10.1016/j.tcs.2011.08.003

• Finite monoid
• Pseudovariety
• Word problem
• Pseudoword
• Omega-term
• Aperiodic
• Regular D-class

In this paper, we solve the word problem for omega-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 omega-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 omega-term.

• 出版日期2011-10-28