000 03314naa a22005297i 4500
001 UMUN-OA-20261005-CS-048
003 local
005 20261005174812.0
006 m o d
007 cr||||||||||||
008 261005s2017 xx o u000 0 eng d
024 7 _a10.1016/j.tcs.2017.06.016
_2doi
035 _a(local)OpenAlex:W2725379159
040 _alocal
_beng
_clocal
041 0 _aeng
100 0 _aTravis Gagie
_eauthor.
245 1 0 _aWheeler graphs: A framework for BWT-based data structures /
_cTravis Gagie; Giovanni Manzini; Jouni Sirén.
264 1 _a[Place of publication not identified] :
_bElsevier BV,
_c2017.
300 _a1 online resource (1 article).
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
500 _aPublication type: Journal article.
500 _aLinked open-access copy: published version.
506 0 _aOpen access; no subscription required for the linked open-access version.
_fUnrestricted online access
_2star
520 3 _aThe famous Burrows–Wheeler Transform (BWT) was originally defined for a single string but variations have been developed for sets of strings, labeled trees, de Bruijn graphs, etc. In this paper we propose a framework that includes many of these variations and that we hope will simplify the search for more. We first define Wheeler graphs and show they have a property we call path coherence. We show that if the state diagram of a finite-state automaton is a Wheeler graph then, by its path coherence, we can order the nodes such that, for any string, the nodes reachable from the initial state or states by processing that string are consecutive. This means that even if the automaton is non-deterministic, we can still store it compactly and process strings with it quickly. We then rederive several variations of the BWT by designing straightforward finite-state automata for the relevant problems and showing that their state diagrams are Wheeler graphs.
540 _aCreative Commons Attribution (licence family recorded by the source; version not supplied in metadata).
_uhttps://openalex.org/W2725379159
546 _aIn English.
588 0 _aDescription generated from OpenAlex bibliographic metadata retrieved on 5 October 2026; full text linked from the source.
590 _aCourse allocation: B. Sc. Computer Science.
650 4 _aBurrows-Wheeler transform
650 4 _afinite automata
650 4 _astate diagrams
650 4 _astring processing
650 4 _ade Bruijn graph
650 4 _alabeled trees
653 _aB. Sc. Computer Science
653 _aUMUN open access collection
653 _adata structures
655 4 _aJournal articles.
700 0 _aGiovanni Manzini
_eauthor.
700 0 _aJouni Sirén
_eauthor.
773 0 _tTheoretical Computer Science
_gVol. 698, (2017), pages/article 67-78
_x0304-3975
856 4 0 _uhttps://www.sciencedirect.com/science/article/pii/S0304397517305285/pdf
_yRead open-access publication
_zOpen access. Access and licence reported by the source; this host could not be independently checked by automation.
_70
884 _aCourse selection and automated MARC21 enrichment from OpenAlex metadata.
_g20261005
_khttps://openalex.org/W2725379159
_qlocal
942 _n0
999 _c410
_d410