Straight-Line Programs: From Compression to Algorithmics

A straight-line program is a context-free grammar that produces exactly one word. The length of this word can be exponentially smaller (in the best case) than the size of the straight-line program. This is the underlying idea of grammar-based compression, where straight-line programs are used for the compression of strings. Compressors that exploit this idea are for instance LZ77, RePair, BiSection, and Sequitur. After introducing straight-line programs and grammar-based compression I will explore recent algorithmic applications of straight-line programs in stringology, group theory, and algebraic complexity theory. If time permits I will also talk about an extension to trees. Straight-line programs for trees have found applications in information theory and parallel algorithms.

Authors

• Markus Lohrey

Keywords

No keywords are indexed for this paper.