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

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