4 papers
Linear-time Minimization of Wheeler DFAs
Jarno Alanko, Nicola Cotumaccio, Nicola Prezza
Wheeler DFAs (WDFAs) are a sub-class of finite-state automata which is playing an important role in the emerging field of compressed data structures: as opposed to general automata…
Wheeler Languages
Jarno Alanko, Giovanna D'Agostino, Alberto Policriti +1
The recently introduced class of Wheeler graphs, inspired by the Burrows-Wheeler Transform (BWT) of a given string, admits an efficient index data structure for searching for subpa…
Regular Languages meet Prefix Sorting
Jarno Alanko, Giovanna D'Agostino, Alberto Policriti +1
Indexing strings via prefix (or suffix) sorting is, arguably, one of the most successful algorithmic techniques developed in the last decades. Can indexing be extended to languages…
Tunneling on Wheeler Graphs
Jarno Alanko, Travis Gagie, Gonzalo Navarro +1
The Burrows-Wheeler Transform (BWT) is an important technique both in data compression and in the design of compact indexing data structures. It has been generalized from single st…