The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete.

Volker Diekert, Claudio Gutierrez, Christian Hagenah

Browse the full STACS paper archive.