Otto, Friedrich; Katsura, Masashi; Kobayashi, Yuji Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids. (English) Zbl 0920.68064 J. Symb. Comput. 26, No. 5, 621-648 (1998). Summary: A finitely presented monoid has a decidable word problem if and only if it can be presented by some left-recursive convergent string-rewriting system if and only if it has a recursive cross-section. However, regular cross-sections or even context-free cross-sections do not suffice. This is shown by presenting examples of finitely presented monoids with decidable word problems that do not admit regular cross-sections, and that, hence, cannot be presented by left-regular convergent string rewriting systems. Also examples of finitely presented monoids with decidable word problems are presented that do not even admit context-free cross-sections. On the other hand, it is shown that each finitely presented monoid with a decidable word problem has a finite presentation that admits a cross-section which is a Church-Rosser language. Finally, we address the notion of left-regular convergent string-rewriting systems that are tractable. \(\copyright\) Academic Press. Cited in 5 Documents MSC: 68Q42 Grammars and rewriting systems Keywords:finitely presented monoid PDFBibTeX XMLCite \textit{F. Otto} et al., J. Symb. Comput. 26, No. 5, 621--648 (1998; Zbl 0920.68064) Full Text: DOI