Confluence problems for trace rewriting systems

Rewriting systems over trace monoids. briefly trace rewriting systems, gene ralize both semi-Thue systems and vector replacement systems. In [21], a pa rticular trace monoid Al is presented such that confluence is undecidable f or the class of length-reducing trace rewriting systems over M. In this pap er, 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 polynomi al time. (C) 2001 Academic Press.