<?xml version="1.0" encoding="UTF-8"?>
<mods xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.loc.gov/mods/v3" version="3.1" xsi:schemaLocation="http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-1.xsd">
  <titleInfo>
    <title>Wheeler graphs: A framework for BWT-based data structures</title>
  </titleInfo>
  <name type="personal">
    <namePart>Travis Gagie</namePart>
    <role>
      <roleTerm authority="marcrelator" type="text">creator</roleTerm>
    </role>
    <role>
      <roleTerm type="text">author.</roleTerm>
    </role>
  </name>
  <name type="personal">
    <namePart>Giovanni Manzini</namePart>
    <role>
      <roleTerm type="text">author.</roleTerm>
    </role>
  </name>
  <name type="personal">
    <namePart>Jouni Sirén</namePart>
    <role>
      <roleTerm type="text">author.</roleTerm>
    </role>
  </name>
  <typeOfResource>text</typeOfResource>
  <genre authority="">Journal articles.</genre>
  <originInfo>
    <place>
      <placeTerm type="code" authority="marccountry">xx</placeTerm>
    </place>
    <dateIssued encoding="marc">2017</dateIssued>
    <issuance>monographic</issuance>
  </originInfo>
  <language>
    <languageTerm authority="iso639-2b" type="code">eng</languageTerm>
  </language>
  <physicalDescription>
    <extent>1 online resource (1 article).</extent>
  </physicalDescription>
  <abstract>The 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.</abstract>
  <note type="statement of responsibility">Travis Gagie; Giovanni Manzini; Jouni Sirén.</note>
  <note>Publication type: Journal article.</note>
  <note>Linked open-access copy: published version.</note>
  <note>Open access; no subscription required for the linked open-access version. Unrestricted online access star</note>
  <note xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="https://openalex.org/W2725379159">Creative Commons Attribution (licence family recorded by the source; version not supplied in metadata). https://openalex.org/W2725379159</note>
  <note>In English.</note>
  <subject>
    <topic>Burrows-Wheeler transform</topic>
  </subject>
  <subject>
    <topic>finite automata</topic>
  </subject>
  <subject>
    <topic>state diagrams</topic>
  </subject>
  <subject>
    <topic>string processing</topic>
  </subject>
  <subject>
    <topic>de Bruijn graph</topic>
  </subject>
  <subject>
    <topic>labeled trees</topic>
  </subject>
  <subject>
    <topic>B. Sc. Computer Science</topic>
  </subject>
  <subject>
    <topic>UMUN open access collection</topic>
  </subject>
  <subject>
    <topic>data structures</topic>
  </subject>
  <relatedItem type="host">
    <titleInfo>
      <title>Theoretical Computer Science</title>
    </titleInfo>
    <identifier type="issn">0304-3975</identifier>
    <part>
      <text>Vol. 698, (2017), pages/article 67-78</text>
    </part>
  </relatedItem>
  <identifier type="uri">https://www.sciencedirect.com/science/article/pii/S0304397517305285/pdf</identifier>
  <location>
    <url displayLabel="Read open-access publication">https://www.sciencedirect.com/science/article/pii/S0304397517305285/pdf</url>
  </location>
  <accessCondition type="restrictionOnAccess">Open access; no subscription required for the linked open-access version.</accessCondition>
  <accessCondition type="useAndReproduction">Creative Commons Attribution (licence family recorded by the source; version not supplied in metadata).</accessCondition>
  <recordInfo>
    <recordContentSource authority="marcorg">local</recordContentSource>
    <recordCreationDate encoding="marc">261005</recordCreationDate>
    <recordChangeDate encoding="iso8601">20261005174812.0</recordChangeDate>
    <recordIdentifier source="local">UMUN-OA-20261005-CS-048</recordIdentifier>
    <languageOfCataloging>
      <languageTerm authority="iso639-2b" type="code">eng</languageTerm>
    </languageOfCataloging>
  </recordInfo>
</mods>
