Conditional semi-Thue Systems for Presenting Monoids
- There are well known examples of monoids in literature which do not admit a finite andcanonical presentation by a semi-Thue system over a fixed alphabet, not even over an arbi-trary alphabet. We introduce conditional Thue and semi-Thue systems similar to conditionalterm rewriting systems as defined by Kaplan. Using these conditional semi-Thue systems wegive finite and canonical presentations of the examples mentioned above. Furthermore weshow, that each finitely generated monoid with decidable word problem is embeddable in amonoid which has a finite canonical conditional presentation.
Author: | Thomas Deiß |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-3073 |
Series (Serial Number): | SEKI Report (92,12) |
Document Type: | Preprint |
Language of publication: | English |
Year of Completion: | 1999 |
Year of first Publication: | 1999 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2000/04/03 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Informatik |
DDC-Cassification: | 0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik |
Licence (German): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |