Word equations, Straight Line Programs, recompression
Artur Jeż
(University of Wrocław)
Course Summary |
About the lecturer |
Location and schedule |
Materials |
Videos
| Assignment
In these series of lectures we will look at some recent results for word equations and grammar compression, called Straight-Line Programs (SLPs) for historic reasons. In a word equations problem we are given a formal equality of two strings over letters and variables and ask for existence of a substitution of variables by strings such that this formal equation is turned into true equality of strings. I will present a simple (to state and analyze) algorithm for this problem using recompression technique, i.e. based on compression and analysis of the compressed form rather than the underlying combinatorics. Then I will discuss some generalizations and open problems. In the second part I will discuss some earlier work on data structures for string equality testing which (among others) inspired the current algorithm, I will also comment on recent progress for this problem. As another topic, I will discuss in more detail the bound on the exponent of periodicity, which was used in the algorithm for word equations in the first lecture. This is a classic result which reduces the problem on word equations to integer programming (i.e. system of linear Diophantine equations). Lastly, we will consider balancing of SLPs: the height of an SLP is the height of the unique derivation tree. Clearly it is Ω(log N), where N is the length of the derived word. I will show that any SLP can be balanced: in linear time we can transform it into an SLP of constant-time larger size, O(log N) height and deriving the same word. I will also quickly comment on strengthening of this result, some application of the approach and of the generalization from SLPs to algebraic circuits.
About the lecturer:Artur Jeż graduated mathematics and computer science at the University of Wrocław in 2006. He pursued his PhD at the same University under the supervision of Krzysztof Loryś and Alexander Okhotin. He completed his PhD thesis on connections between Conjunctive Grammars and Equations over Sets of Natural Numbers in 2010. He was employed as assistant professor at the University of Wrocław in 2010–2012 and then he was a postdoc at Max Planck Institute for Computer Science (Saarbruecken, Germany) in 2012–14, most of the time as a Humboldt Foundation fellow. Afterwards he returned to Wrocław, in 2015 he received habilitation and since 2018 he is an associate professor. In recent years Artur Jeż is mostly interested in grammar compression and its connections to word equations and similar topics.
Location and schedule:ZOOM – link sent upon registration. The lectures will be recorded and posted below after each lecture.
|
|
|
||||||||||||||||||