Infinite Convergent String-rewriting Systems and Cross-sections for Finitely Presented Monoids
✍ Scribed by F. OTTO; M. KATSURA; Y. KOBAYASHI
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 635 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0747-7171
No coin nor oath required. For personal study only.
✦ Synopsis
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.