AbstractThe exponent of periodicity is an important factor in estimates of complexity of word-unification algorithms. We prove that the exponent of periodicity of a minimal solution of a word equation is of order 2^{1.07d}, where d is the length of the equation. We also give a lower bound 2^{0.29d}, so our upper bound is almost optimal and exponentially better than the original bound (6d)^{2^{2d^4}} + 2. Consequently, our result implies an exponential improvement of known upper bounds on complexity of word-unification algorithms.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; I.1.2 [Algebraic Manipulation]: Algorithms -- algebraic algorithms
General Terms: Algorithms, complexity, equations
Additional Key Words and Phrases: Diophantine equation, periodicity, semantic unification, semigroups, word equations
Selected papers that cite this one
- Antoni Ko\'scielski and Leszek Pacholski. Makanin's algorithm is not primitive recursive. Theoretical Computer Science, 191(1-2):145-156, 30 January 1998.
Selected references
- H. Abdulrab and J. P. P[?]cuchet. Associative unification. Journal of Symbolic Computation, 8(5):499-522, November 1989.
- Joxan Jaffar. Minimal and complete word unification. Journal of the ACM, 37(1):47-85, January 1990.