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.
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.
