An efficient algorithm for solving word equations
Wojciech Plandowski · 2006
We present the first DEXPTIME algorithm which solves word equations i.e. finds a finite representation of all solutions of an equation in a free semigroup. We show how to use our approach to solve two new problems in PSPACE which deal with properties of the solution set of a word equation: