×

Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids. (English) Zbl 0920.68064

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.

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI