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.

Podrobná bibliografie
Vydáno v:Journal of the ACM 51, 3 (2004).
Hlavní autor: Plandowski, Wojciech
Médium: Článek
Jazyk:English
Témata:
Theory of computation.
Mathematical logic and formal languages.
Formal languages.
Decision problems.
Theory.