Aufsatz in einer Fachzeitschrift
Some results on Green's relations for monoids presented by monadic string-rewriting systems
Details zur Publikation
Autor(inn)en: | Otto, F. |
Publikationsjahr: | 2002 |
Zeitschrift: | Semigroup Forum |
Seitenbereich: | 374-385 |
Jahrgang/Band : | 65 |
ISSN: | 0037-1912 |
Zusammenfassung, 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.
