A finitely presented monoid has a decidable word problem if and only if it has a recursive cross-section if and only if it can be presented by some left-recursive convergent string-rewriting system. 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 stringrewriting 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.
Acknowledgement: The results presented here were obtained while the first author was visiting at the Department of Information Science of Toho University and the Department of Mathematics of Kyoto Sangyo University in the spring of 1996. He gratefully acknowledges the hospitality of these two departments and the support by the Deutsche Forschungsgemeinschaft.