Some results on Green's relations for monoids presented by monadic string-rewriting systems (Q1849636)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Some results on Green's relations for monoids presented by monadic string-rewriting systems |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some results on Green's relations for monoids presented by monadic string-rewriting systems |
scientific article |
Statements
Some results on Green's relations for monoids presented by monadic string-rewriting systems (English)
0 references
1 December 2002
0 references
\textit{R. V. Book} [Theor. Comput. Sci. 24, 301-312 (1983; Zbl 0525.68015)] proved that for finite monadic confluent string-rewriting systems, the validity of linear sentences is decidable and stated that all the Green relations are decidable. However, it is not clear that the Green relation \(\mathcal D\) is expressed by a linear sentence. The author fills this gap and shows that \(\mathcal D\) is actually decidable in polynomial time for such systems. He proves this result by showing that the sets of irreducible strings in the \(\mathcal R\)-class and in the \(\mathcal D\)-class are regular sets.
0 references
finite monadic confluent string-rewriting systems
0 references
Green relations
0 references
decidability
0 references
irreducible strings
0 references
regular sets
0 references