Recompression: A Simple and Powerful Technique for Word Equations

In this article, we present an application of a simple technique of local recompression, previously developed by the author in the context algorithms for compressed strings [Jez 2014a, 2015b, 2015a], to word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and iterative replacement of pairs of letters occurring in the equation by a "fresh" letter, which can be seen as a bottom-up compression of the solution of the given word equation, or, to be more specific, building a Straight-Line Programme for the solution of the word equation. Using this technique, we give new, independent, and self-contained proofs of many known results for word equations. To be more specific, the presented (nondeterministic) algorithm runs in O(nlog n) space and in time polynomial in n and log N, where n is the size of the input equation and N the size of the length-minimal solution of the word equation. Furthermore, for O(1) variables, the bound on the space consumption is in fact linear, that is, O(m), where m is the size of the space used by the input. This yields that for each k the set of satisfiable word equations with k variables is context sensitive. The presented algorithm can be easily generalised to a generator of all solutions of the given word equation (without increasing the space usage). Furthermore, a further analysis of the algorithm yields an independent proof of doubly exponential upper bound on the size of the length-minimal solution. The presented algorithm does not use exponential bound on the exponent of periodicity. Conversely, the analysis of the algorithm yields an independent proof of the exponential bound on exponent of periodicity.