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.

Metadaten
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