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

Burrows-Wheeler transformfinite automatagraph indexingregular languagesWheeler 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

• 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
• 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 7123551 (Why is no real title available?)
• 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
• On the complexity of string matching for graphs
• 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

(21)

• Circular languages
• Solving string problems on graphs using the labeled direct product
• On the complexity of recognizing Wheeler graphs
• Ordering regular languages and automata: complexity
• scientific article; zbMATH DE number 3862470 (Why is no real title available?)
• scientific article; zbMATH DE number 1408330 (Why is no real title available?)
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• scientific article; zbMATH DE number 6606384 (Why is no real title available?)
• A new class of string transformations for compressed text indexing
• Optimal Wheeler language recognition
• Space-time trade-offs for the LCP array of Wheeler DFAs
• Cascade products and Wheeler automata
• On the complexity of computing the co-lexicographic width of a regular language
• Universally Wheeler languages
• Completing Wheeler automata
• The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching
• The rational construction of a Wheeler DFA
• Random Wheeler automata
• A Myhill-Nerode theorem for generalized automata, with applications to pattern matching and compression
• Co-lexicographically ordering automata and regular languages. I
• Generalized Wheeler automata: minimality

Describes a project that uses

Uses Software

• BWA
• vg
• r-index

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)