On the Complexity of Solving Restricted Word Equations

摘要

We investigate the complexity of the solvability problem for restricted classes of word equations with and without regular constraints. The solvability problem for unrestricted word equations remains NP-hard, even if, on both sides, between any two occurrences of the same variable no other different variable occurs; for word equations with regular constraints, the solvability problems remains NP-hard for equations whose two sides share no variables or with two variables, only one of which is repeated. On the other hand, word equations with only one repeated variable (but an arbitrary number of variables) and at least one non-repeated variable on each side, can be solved in polynomial-time.