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

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