Wheeler languages

DOI10.1016/j.ic.2021.104820OpenAlexW4205775169MaRDI QIDQ2051845

Jarno Alanko, Nicola Prezza, Giovanna D'Agostino, Alberto Policriti

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.10303

zbMATH Keywords

finite automataregular languagesBurrows-Wheeler transformgraph indexingWheeler languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

A new class of string transformations for compressed text indexing ⋮ Ordering regular languages and automata: complexity ⋮ Solving string problems on graphs using the labeled direct product ⋮ On the complexity of recognizing Wheeler graphs

Uses Software

• vg
• BWA
• r-index

Cites Work

• Lightweight algorithms for constructing and inverting the BWT of string collections
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Wheeler graphs: a framework for BWT-based data structures
• Lengths of words accepted by nondeterministic finite automata
• An extension of the Burrows-Wheeler transform
• Suffix Arrays: A New Method for On-Line String Searches
• Indexing compressed text
• Succinct de Bruijn Graphs
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• Regular Languages meet Prefix Sorting
• Indexing Variation Graphs
• The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Wheeler languages