Ph.D XXXVI

Supervisor: Alberto Policriti, Giovanna DʼAgostino

Phone: +39 0432 558411 

Room: Rizzi NS4

Mail: martincigh.davide@spes.uniud.it 

Research Project

Wheeler Automata, a generalization of the Burrow-Wheeler transformation

The Burrows-Wheeler Transformation (for brevity BWT) is a tool used in lossless string compression to transform an highly repetitive string into another one which will end up to be more compressible than the original one. Along with the Lempel- Ziv Algorithm, the BWT is one of the most notorious and most used method to compress highly repetitive strings.

In 2017 Gagie, Manzini and Siren published an article where they introduced the Wheeler graphs, a generalization of the BWT. Using this kind of graphs, it’s possible to compress not only a single string, but a collection of strings all at once using an extremely efficient data structure that support fast queries on the original strings.

The aim of my PhD is to further analyze the properties of Wheeler Automa, i.e. Automata whose undelying graph is a Wheeler graph, and the languages recognized by such Automata.