Satisfiability of word equations with constants is in PSPACE.

We prove that satisfiability problem for word equations is in PSPACE.

Dettagli Bibliografici

Pubblicato in:	Journal of the ACM 51, 3 (2004).
Autore principale:	Plandowski, Wojciech
Natura:	Articolo
Lingua:	English
Soggetti:	Theory of computation. Mathematical logic and formal languages. Formal languages. Decision problems. Theory.