Access Restriction

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

   Open content in new tab
Source: ACM Digital Library