Satisfiability of Word Equations with Constants is in NEXPTIME.

Wojciech Plandowski

Browse the full STOC paper archive.