An automata-theoretic approach to the word problem for omega-terms over R

摘要

This paper studies the pseudovariety R of all finite R-trivial semigroups. We give a representation of pseudowords over R by infinite trees, called R-trees. Then we show that a pseudoword is an omega-term if and only if its associated tree is regular (i.e. it can be folded into a finite graph), or equivalently, if the w-term has a finite number of tails. We give a linear algorithm to compute a compact representation of the R-tree for omega-terms, which yields a linear solution of the word problem for omega-terms over R. We finally exhibit a basis for the omega-variety generated by R and we show that there is no finite basis. Several results can be compared to recent work of Bloom and Choffrut on long words. (c) 2006 Elsevier B.V. All rights reserved.