Various applications of local recompression technique
Спикер: Artur Jeż, получил степень PhD в Вроцлавском университете под руководством Кшиштофа Лорис и Александра Охотина, защитив диссертацию о связях между конъюнктивными грамматиками и уравнениями над множествами натуральных чисел в 2010 году. Работал в Польше и Германии, также был стипендиатом Фонда Гумбольдта. Сейчас Артур работает доцентом Вроцлавского университета и больше всего интересуется сжатием грамматики и ее связью со словесными уравнениями и подобными темами.
In this series of lectures I will talk about various applications of local recompression technique, which is applicable to data given in an implicit way, for instance as solutions of equations, or in a compressed form. The technique applies simple compression operations (replacement of pairs of letters) and modifying the instance so that this is possible directly on the implicit representation.
1 Word equations, compression-based algorithms In word equation problem we are given an equation of the form u = v, where u, v are words of letters and variables, and ask whether there is a substitution of variables by letters so that this formal equality is turned into true equality of words. Using the recompression technique I will give a self-contained algorithm that works in polynomial space for word equations. Although algorithm with similar such bounds were known, the proposed algorithm is much simpler, has simpler proof and the space usage is smaller.
2 Extensions and variants of the algorithm for word equations.
In the second lecture I will discuss several improvements of the algorithm: smaller space consumption, treatment of regular constraints, variants working for equations over free groups, representation of all solutions, and comment on further generalizations into similar algebraic objects (traces, ...).
3 Context unification Contexts are terms with one `hole', i.e. a place in which we can substitute an argument and in context unification we are given an equation over terms with variables representing contexts and ask about the satisfiability of this equation. For instance, the equation f(X(c),X(c)) = X(f(c,c)) has exactly one solution: X = •, Context unification generalizes word equations, which are decidable, and are generalized by second order unification, which is undecidable. The decidability status of context unification was open for more than 20 years. I will show how to generalize the recompression technique from words to terms, this is in particular gives a polynomial space algorithm for context unification.
4 Grammar compression for words and trees In grammar compression we represent an input word w as a context free grammar generating a unique word: w. In the smallest grammar problem we ask, given a word w, for a smallest context free grammar generating this word. It is known that the decision variant of this problem is NP-complete, and algorithms with approximation ratio log|w| are known. We give two approximation algorithms for this problem based on recompression technique, both matching the bound on approximation ratio. One is very simple, the other more involved, but can be generalized to the case when we want to represent an input tree as context free tree grammar (generating a unique tree). This was the first known approximation algorithm for this problem.
5 Efficient variants: equality of straight line-programs, compressed pattern matching. The growing size of data lead to development on algorithm that process compressed data directly, without the explicit decompression. We show that the recompression technique can be applied to one of basic problem: the equality of two different grammar compressed strings. I also discuss the generalization of the problem of pattern matching. Finally I will describe some older structures that for this problem that led to development of the recompression technique, I will also comment on some newer variants on those data structures.