2026-07-24T18:11:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23920 2026-02-09T06:23:59Z ddc:004 open_access

Wheeler Graphs and Wheeler Languages Cotumaccio, Nicola D'Agostino, Giovanna Gibney, Daniel Policriti, Alberto Prezza, Nicola Thankachan, Sharma V. Wheeler languages Wheeler graphs pattern matching indexing compressed data structures Suffix sorting stands at the core of the most efficient solutions for indexed pattern matching: the suffix tree, the suffix array, compressed indexes based on the Burrows-Wheeler transform, and so on. In [Gagie, Manzini, Sirén, TCS 2017] this concept was extended to labeled graphs, obtaining the rich class of Wheeler graphs. This work opened a very fruitful line of research, ultimately generating results able to bridge the fields of compressed data structures, graph theory, and regular language theory. In a Wheeler graph, nodes are sorted according to the alphabetic order of their incoming labels, propagating this order through pairs of equally-labeled edges. This apparently-simple definition makes it possible to solve on Wheeler graphs problems (including, but not limited to: compression, subpath queries, NFA equivalence, determinization, minimization) that on general labeled graphs are extremely hard to solve, and induces a rich structure in the class of regular languages (Wheeler languages) recognized by automata whose state transition is a Wheeler graph. The goal of this survey is to provide a summary of (and intuitions behind) the results on Wheeler graphs that appeared in the literature since their introduction, in addition to a discussion of interesting problems that are still open in the field. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicola Cotumaccio and Giovanna D'Agostino and Daniel Gibney and Alberto Policriti and Nicola Prezza and Sharma V. Thankachan 2025 Is Part Of OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Manzini.12 urn:nbn:de:0030-drops-239205 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.12 eng https://creativecommons.org/licenses/by/4.0/legalcode