Wheeler languages

DOI10.1016/J.IC.2021.104820MaRDI QIDQ2051845zbMATH OpenOpenAlexFDO

Authors Jarno Alanko, Giovanna D'Agostino, Nicola Prezza, 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 languagesgraph indexingBurrows-Wheeler transformWheeler languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Wheeler graphs: a framework for BWT-based data structures
• On the complexity of recognizing Wheeler graphs
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• When a dollar makes a BWT
• Two combinatorial criteria for BWT images

Cites work

• scientific article; zbMATH DE number 3473324 (Why is no real title available?)
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• scientific article; zbMATH DE number 7561548 (Why is no real title available?)
• scientific article; zbMATH DE number 7123551 (Why is no real title available?)
• An extension of the Burrows-Wheeler transform
• First-order definable languages
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Indexing compressed text
• Indexing variation graphs
• Lengths of words accepted by nondeterministic finite automata
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Regular Languages meet Prefix Sorting
• Succinct de Bruijn graphs
• Suffix Arrays: A New Method for On-Line String Searches
• The Burrows-Wheeler transform between data compression and combinatorics on words
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Wheeler graphs: a framework for BWT-based data structures

Cited in

(11)

• scientific article; zbMATH DE number 1408330 (Why is no real title available?)
• A new class of string transformations for compressed text indexing
• scientific article; zbMATH DE number 3862470 (Why is no real title available?)
• On the complexity of recognizing Wheeler graphs
• Circular languages
• Cascade products and Wheeler automata
• scientific article; zbMATH DE number 6606384 (Why is no real title available?)
• Ordering regular languages and automata: complexity
• Solving string problems on graphs using the labeled direct product
• Optimal Wheeler language recognition
• Space-time trade-offs for the LCP array of Wheeler DFAs

Describes a project that uses

Uses Software

• r-index
• BWA
• vg

This page was built for publication: Wheeler languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051845)