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 Al 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. (C) 2001 Academic Press.