Conditional semi-Thue Systems for Presenting Monoids

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 each finitely generated monoid with decidable word problem is embeddable in a monoid which has a finite canonical conditional presentation.