Word equations, Straight Line Programs, recompression

Artur Jeż (University of Wrocław)

Course Summary | About the lecturer | Location and schedule | Materials | Videos | Assignment

Course summary:

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.

Thursday, November 25
14:15 - 15:45 lecture
16:15 - 17:15 class
Friday, November 26
14:15 - 15:45 lecture
16:15 - 17:15 class
Saturday, November 27
10:15 - 11:45 lecture
12:15 - 13:15 class


Videos: The video recordings of the lectures are now available.
Assignment: assignment. Due: end of December, 2021.