Wheeler languages

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 subpaths with a given path label, and lifts the applicability of the Burrows-Wheeler Transform from a single string to an entire language. In this paper we study the regular languages accepted by automata having a Wheeler graph as transition function and prove results on determinization, Myhill-Nerode characterization, decidability, and closure properties for this class of languages.

Authors

• Jarno Alanko
• Giovanna D'Agostino
• Alberto Policriti
• Nicola Prezza

Keywords

• Regular languages
• Finite automata
• Burrows-Wheeler transform
• Wheeler languages
• Graph indexing