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.07

d}, wheredis 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.