Solving word equations modulo partial commutations
it is shown that it is decidable whether an equation over a free partially commutative monoid has a solution. We give a proof of this result using normal forms. Our method is a direct reduction of a trace equation system to a word equation system with regular constraints. Hereby we use the extension of Makanin's theorem on the decidability of word equations to word equations with regular constraints, which is due to Schulz. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
word equations partial commutations traces word equations with regular constraints