Satisfiability of Word Equations with Constants is in PSPACE.

Wojciech Plandowski

Browse the full FOCS paper archive.