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.
Wheeler Languages
Giovanna D'Agostino
Secondo
;Alberto PolicritiPenultimo
;
2021-01-01
Abstract
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
I_C_Wheeler_Languages.pdf
non disponibili
Descrizione: Articolo principale
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non pubblico
Dimensione
580.15 kB
Formato
Adobe PDF
|
580.15 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
