Resolution of the Burrows-Wheeler transform conjecture

DOI10.1109/FOCS46700.2020.00097MaRDI QIDQ6943958zbMATH OpenFDO

Authors Dominik Kempa, Tomasz Kociumaka

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00097

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(8)

• Computing NP-hard repetitiveness measures via MAX-SAT
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Generalized straight-line programs
• Computing MEMs and relatives on repetitive text collections
• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• Non-overlapping indexing in BWT-runs bounded space
• Exploiting new properties of string net frequency for efficient computation
• Internal pattern matching in small space and applications

This page was built for publication: Resolution of the Burrows-Wheeler transform conjecture

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