Computer Science – Formal Languages and Automata Theory
Scientific paper
2012-03-16
Computer Science
Formal Languages and Automata Theory
Scientific paper
In this paper we present an application of a simple technique of local recompression, previously developed by the author in the context of compressed membership problems and compressed pattern matching, to word equations. The technique is based on iterative replacement of pairs of letters appearing in the equation by a `fresh' letter and local modification of variables (replacing X by aX or Xa). The interesting feature of this technique is that it, and its application, do not require any understanding of the word equations nor of their solutions, which is rather uncommon in the area. Using this technique we give a new, independent and completely self-contained proofs of most of the known results for equations. To be more specific, the presented (nondeterministic) algorithm runs in polynomial space and in time polynomial in log N, where N is the size of the length-minimal solution of the word equation. Both upper bounds were previously attained, though by separate and completely different algorithms. 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 simple analysis of the algorithm yields a 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, only its weaker version which is concerned with blocks of one letter only (a relatively short and simple proof is supplied), conversely, the analysis of the algorithm yields an independent proof of the exponential bound on exponent of periodicity. We believe that the presented algorithm, its idea and analysis are far simpler than all previously applied. Furthermore, thanks to it we can obtain a unified and simple approach to most of known results for word equations.
No associations
LandOfFree
Recompression: a simple and powerful technique for word equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Recompression: a simple and powerful technique for word equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recompression: a simple and powerful technique for word equations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-351899