The 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) 22d4 + 2 . Consequently, our result implies an exponential improvement of known upper bounds on complexity of word-unification algorithms.

It is proved that the exponent of periodicity of a minimal solution of a word equation is at most 2/sup 2.54n/, where n is the length of the equation. Since the best known lower bound is 2/sup 0.31n/, this upper bound is almost optimal and exponentially better than the original bound. Thus the result implies exponential improvement of known upper bounds on complexity of word-unification algorithms. Evidence is given that, contrary to common belief, the algorithm deciding satisfiability of equations in free groups, given by G.S. Makanin (1977), is not primitive recursive.>