### Recompression: A Simple and Powerful Technique for Word EquationsRecompression: A Simple and Powerful Technique for Word Equations

Access Restriction
Subscribed

 Author Je, Artur Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Exponent of periodicity ♦ Semantic unification ♦ String unification ♦ Word equations Abstract 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 [Jeż 2014a, 2015b, 2015a], to word equations. The technique is based on local modification of variables (replacing $\textit{X}$ by $\textit{aX}$ or $\textit{Xa})$ and iterative replacement of pairs of letters occurring in the equation by a “fresh” letter, which can be seen as a bottom-up $\textit{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 $\textit{O}(\textit{n}$ log $\textit{n}$ space and in time polynomial in $\textit{n}$ and log $\textit{N},$ where $\textit{n}$ is the size of the input equation and $\textit{N}$ the size of the length-minimal solution of the word equation. Furthermore, for $\textit{O}(1)$ variables, the bound on the space consumption is in fact linear, that is, $\textit{O}(\textit{m}),$ where $\textit{m}$ is the size of the space used by the input. This yields that for each $\textit{k}$ the set of satisfiable word equations with $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-02-12 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 1 Page Count 51 Starting Page 1 Ending Page 51

#### Open content in new tab

Source: ACM Digital Library