An efficient algorithm for solving word equations

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: deciding finiteness of the solution set, deciding boundness of the set of maximal exponents of periodicity of solutions.

Authors

• Wojciech Plandowski

Keywords

No keywords are indexed for this paper.