Moses Ganardi

"Straight-Line Programs: From Compression to Verification"

With ever-increasing amounts of data, we are faced with the challenge of compactly storing and efficiently processing these massive data sets. One important objective is to design compressed data structures and algorithms that allow us to access, query, and manipulate the data directly in compressed form without prior decompression.
One popular compression scheme which captures many dictionary-based compressors is grammar-based compression, based on the notion of straight-line programs. Their simple, hierarchical definition makes straight-line programs amenable to algorithms that work directly on the compressed representation. Furthermore, straight-line programs are crucially used as intermediate data structures in various domains, ranging from verification, word equations, algorithmic group theory to algebraic complexity theory.
In this talk, we will present a line of work on the generic preprocessing technique of balancing straight-line programs. Balancing has improved and simplified various algorithmic results on compressed data. Moreover, we will highlight a recent application of straight-line programs in the verification of multithreaded programs.

Termin als Datei downloaden und in den Kalender importieren.