Satisfiability of word equations with constants is in PSPACE.

Satisfiability of word equations with constants is in PSPACE.

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

Sonraí bibleagrafaíochta
Foilsithe in:Journal of the ACM 51, 3 (2004).
Príomhchruthaitheoir: Plandowski, Wojciech
Formáid: Alt
Teanga:English
Ábhair:
Theory of computation.
Mathematical logic and formal languages.
Formal languages.
Decision problems.
Theory.