Recompression-based PSPACE algorithm for word equations.

Speaker(s)

Artur Jeż

Affiliation

Uniwersytet Wrocławski

Date

May 16, 2012, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

In this talk I will present an application of a simple technique of local recompression, 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). This can be seen as a bottom-up compression of the solution of the given word equation, to be more specific, an SLP (Straight-Line Programme) for the solution of the word equation is built in this way. 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.

Using this technique I will give a new, independent and self-contained proofs of most of the known results for word 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).  A further 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,
conversely, the analysis of the algorithm yields an independent proof of the exponential bound on exponent of periodicity.

The technique can be also applied to SLP-related problems, like fully compressed pattern matching (yielding a quadratic algorithm) or fully compressed membership problem for NFAs (yielding an NP algorithm).

---