Abstract
There are well known examples of monoids in literature which do not admit a finite and canonical presentation by a semi-Thue system over a fixed alphabet, not even over an arbitrary alphabet. We introduce conditional Thue and semi-Thue systems similar to conditional term rewriting systems as defined by Kaplan. Using these conditional semi-Thue systems we give finite and canonical presentations of the examples mentioned above. Furthermore we show, that every finitely generated monoid with decidable word problem is embeddable in a monoid which has a finite canonical conditional presentation.
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
Günther Bauer. Zur Darstellung von Monoiden durch konfluente Regelsysteme. PhD thesis, Fachbereich Informatik, Universität Kaiserslautern, 1981. in German.
Ronald V. Book. Thue systems as rewriting systems. In Proc. of 1st Rewriting Techniques and Applications, pages 63–94. Springer, 1985. LNCS 202.
Martin D. Davis. A note on universal turing machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, pages 167–175. Princeton Press, 1956.
Martin D. Davis and Elaine J. Weyuker. Computability, Complexity, and Languages. Academic Press, 1983.
Harald Ganzinger. A completion procedure for conditional equations. Technical Report 234, Fachbereich Informatik, Universität Dortmund, 1987.
Gérard Huet. Confluent reductions: Abstract properties and applications to term rewriting systems. Journal of the ACM, 27(4):797–821, oct 1980.
Matthias Jantzen. Confluent String Rewriting. Springer, Berlin, Heidelberg, New York, 1988.
Jean Pierre Jouannaud and Bernard Waldmann. Reductive conditional term rewriting systems. In Proceedings of the 3rd IFIP Working Conference on Formal Description of Programming Concepts. North-Holland, 1986.
Stephane Kaplan. Conditional rewrite rules. Theoretical Computer Science, 33:175–193, 1984.
Stephane Kaplan. Simplifying conditional term rewriting systems: Unification, termination and confluence. Journal of Symbolic Computation, 4:295–334, 1987.
Helene Kirchner and Miki Hermann. Computing meta-rules from crossed rewrite systems. Technical report, CRIN, Nancy, 1989.
Deepak Kapur and Paliath Narendran. A finite Thue system with decidable word problem and without equivalent finite canonical system. Theoretical Computer Science, 35:337–344, 1985.
Zohar Manna. Mathematical Theory of Computation. Computer Science Series. McGraw-Hill, 1974.
Andrea Sattler-Klein. Divergence phenomena during completion. In Ronald V. Book, editor, Proc. of 4th Rewriting Techniques and Applications, pages 374–385. Springer, 1991. LNCS 488.
C. C. Sims. Verifying nilpotence. Journal of Symbolic Computation, 3:231–247, 1987.
Craig Squier. Word problems and a homological finiteness condition for monoids. Journal of pure and applied algebra, 49:201–217, 1987.
Craig Squier. A finiteness condition for rewriting systems. Department of Mathematical Sciences, SUNY-Binghamton, Binghamton, NY 13901, 1988.
J. C. Shepherdson and H. E. Sturgis. Computability of recursive functions. Journal of the ACM, 10:217–255, 1963.
Jörg Siekmann and P. Szabo. A noetherian and confluent rewrite system for idempotent semigroups, semigroup forum, 25:83–110, 1982.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Deiß, T. (1992). Conditional semi-Thue systems for presenting monoids. In: Finkel, A., Jantzen, M. (eds) STACS 92. STACS 1992. Lecture Notes in Computer Science, vol 577. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55210-3_212
Download citation
DOI: https://doi.org/10.1007/3-540-55210-3_212
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55210-9
Online ISBN: 978-3-540-46775-5
eBook Packages: Springer Book Archive