Journal article
Some results on Green's relations for monoids presented by monadic string-rewriting systems



Publication Details
Authors:
Otto, F.
Publication year:
2002
Journal:
Semigroup Forum
Pages range:
374-385
Volume number:
65
ISSN:
0037-1912

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.


Authors/Editors

Last updated on 2019-01-11 at 16:03