Confluence Problems for Trace Rewriting Systems

Rewriting systems over trace monoids, briefly trace rewriting systems, generalize both semi-Thue systems and vector replacement systems. In [21], a particular trace monoid M is presented such that confluence is undecidable for the class of length–reducing trace rewriting systems over M. In this paper, we show that this result holds for every trace monoid, which is neither free nor free commutative. Furthermore we show that confluence for special trace rewriting systems over a fixed trace monoid is decidable in polynomial time.

Authors

• Markus Lohrey

Keywords

No keywords are indexed for this paper.