[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #92

Originator: Klaus Schulz
Date: September 1998

Summary: What is the exact complexity of word unification?

Satisfiability of word equations, that is unifiability in the algebra of ground terms built on a set of constants and a binary, associative concatenation operator, has been shown decidable by [Mak77], see [Die02] for a recent presentation of Makanin’s algorithm. The best known upper bounds for its complexity are exponential space and doubly exponential time ([Gut98]), leaving a wide gap to the best known lower bound of its complexity which is just NP (see [Die02]). There is an strange discrepancy between this weak lower bound and the enormous difficulty in designing word unification algorithms. So, what is the exact complexity of word unification?

Remark

Satisfiability of word equations is in PSPACE [Pla99].

References

[Die02]
Volker Diekert. Makanin’s algorithm. In M. Lothaire, editor, Algebraic Combinatorics on Words, chapter 12, pages 387–442. Cambridge University Press, 2002.
[Gut98]
C. Gutiérrez. Satisfiability of word equations with constants is in exponential space. In Proceedings of the 39th Symposium on Foundations of Computer Science, 1998.
[Mak77]
G. S. Makanin. The problem of solvability of equations in a free semi-group. Math. USSR Sbornik, 32(2):129–198, 1977.
[Pla99]
Wojciech Plandowski. Satisfiability of word equations with constants is in PSPACE. In Proceedings of the 40th Symposium on Foundations of Computer Science, pages 495–500, New York, NY, USA, October 1999. IEEE.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]