Some results on Green's relations for monoids presented by monadic string-rewriting systems (Q1849636)

From MaRDI portal





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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references