Conditional  semi-Thue  Systems  for  Presenting  Monoids

Thomas Deiss

Fachbereich Informatik, Universitaet Kaiserslautern
Postfach 3049, D-6750 Kaiserslautern
Email: deiss@informatik.uni-kl.de

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 presen-
tations of the examples mentioned above.  Furthermore we show, that each fini-
tely generated  monoid with  decidable word problem  is embeddable in a monoid
which has a finite canonical conditional presentation.

Keywords:
Conditional Rewriting, Thue Systems, word problem

Source
anonymous FTP server ftp.uni-kl.de [131.246.94.94]
path: /reports_uni-kl/computer_science/SEKI/1992/papers
file: Deiss.SR-92-12.english.ps.Z