Journal article
Some results on Green's relations for monoids presented by monadic string-rewriting systems
Publication Details
Abstract
For finite monadic string-rewriting systems that are confluent and for finite special string-rewriting systems that are lambda-confluent it is shown that the R-class and the L-class of a string can be characterized by a regular set of irreducible strings. It follows that for these systems the relation D is decidable. Actually it is shown that this relation is decidable in polynomial time.