Data Compression Meets Automata Theory
Nicola Cotumaccio · Työväentutkimus Vuosikirja · 2025
I received my PhD in Computer Science on January 31, 2024, under a Joint PhD agreement between Gran Sasso Science Institute (L'Aquila, Italy) and Dalhousie University (Halifax, Canada). I was supervised by Travis Gagie, Nicola Prezza and Catia Trubiani. My PhD thesis, Data Compression Meets Automata Theory, was selected by the Italian Chapter of the EATCS for the Best PhD Thesis Award. The thesis introduces a new paradigm for studying regular languages, establishing a connection between classical results in automata theory, such as the powerset construction, and the most important data structures for solving pattern matching queries on compressed strings, such as the Burrows- Wheeler transform. The results and the open problems should be of interest to both the algorithmic community and the formal language theory community.