The word problem for \(\omega \)-terms over DA (Q650888)

The pseudovariety DA is the class of finite monoids whose regular \(\mathcal{D}\)-classes are aperiodic semigroups. The present paper solves \(\omega\)-terms over DA; this problem asks for an algorithm which decides if two given \(\omega\)-terms are equal over all elements of this pseudovariety. In an earlier paper of the author [Int. J. Algebra Comput. 21, No. 5, 675--701 (2011; Zbl 1243.20070)] some representations of implicit operations over DA were given; here the representation by quasi-ternary labeled trees has been improved, which contains the infinite case consisting of wrapping the DA-trees of an implicit operation. Another representation is given by means of DA-automata, and it is proved that an \(\omega\)-term has a finite representation by the minimal DA-automaton. These minimal DA-automata associated to an \(\omega\)-term are computed in polynomial time.