Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.I. Adian. The Burnside Problem and Identities in Groups. Springer-Verlag, Berlin, 1979.
J. Avenhaus. On the descriptive power of term rewriting systems. J. Symbolic Computation, 2:109–122, 1986.
J. Berstel. Transductions and Context-free Languages. Teubner Studienbücher. Teubner-Verlag, 1979.
R.V. Book and F. Otto. String-Rewriting Systems. Springer-Verlag, New York, 1993.
G. Buntrock and F. Otto. Growing context-sensitive languages and Church-Rosser languages. In E.W. Mayr and C. Puech, editors, Proc. of STACS 95, Lecture Notes in Computer Science 900, pages 313–324. Springer-Verlag, Berlin, 1995.
G. Buntrock. Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakultät für Mathematik und Informatik, Universität Würzburg, 1996.
R.H. Gilman. Groups with a rational cross-section. In S.M. Gersten and J.R. Stallings, editors, Computational Group Theory and Topology, pages 175–183. Princeton, 1987.
Y. Kobayashi. A finitely presented monoid which has solvable word problem but has no regular complete presentation. Theoretical Computer Science, 146:321–329, 1995.
R. McNaughton, P. Narendran, and F. Otto. Church-Rosser Thue systems and formal languages. Journal Association Computing Machinery, 35:324–344, 1988.
A. Sattler-Klein. Divergence phenomena during completion. In R.V. Book, editor, Rewriting Techniques and Applications, pages 374–385. Springer-Verlag, Berlin, 1991. Lecture Notes in Computer Science 488.
C.C. Squier. Word problems and a homological finiteness condition for monoids. J. Pure Applied Algebra, 49:201–217, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Otto, F., Katsura, M., Kobayashi, Y. (1997). Cross-sections for finitely presented monoids with decidable word problems. In: Comon, H. (eds) Rewriting Techniques and Applications. RTA 1997. Lecture Notes in Computer Science, vol 1232. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62950-5_61
Download citation
DOI: https://doi.org/10.1007/3-540-62950-5_61
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62950-4
Online ISBN: 978-3-540-69051-1
eBook Packages: Springer Book Archive