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. (C) 2021 Elsevier Inc. All rights reserved.

Wheeler languages

Prezza, N
2021

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. (C) 2021 Elsevier Inc. All rights reserved.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0890540121001504-main.pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso chiuso-personale
Dimensione 720.52 kB
Formato Adobe PDF
720.52 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/5004032
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact