2020/02/24 by Jarno Alanko, Alanko, Jarno, Giovanna D’Agostino +5
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Network Packet Processing and Optimization #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2002.10303
openalex publication_date 2020/02/24 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
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 strings to languages. In this paper we study the regular languages accepted by automata having a Wheeler graph as transition function, and prove results on determination, MyhillNerode characterization, decidability, and closure properties for this class of languages.