Substring complexities on run-length compressed strings
From MaRDI portal
Publication:6111584
DOI10.1007/978-3-031-20643-6_10zbMath1525.68042arXiv2205.12421OpenAlexW4312828769MaRDI QIDQ6111584
Itagaki Tomohiro, Akiyoshi Kawamoto
Publication date: 4 August 2023
Published in: String Processing and Information Retrieval (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2205.12421
Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Cites Work
- Sorting in linear time?
- Universal compressed text indexing
- Collage system: A unifying framework for compressed pattern matching.
- Towards a definitive measure of repetitiveness
- A combinatorial view on string attractors
- Sublinear algorithms for approximating string compressibility
- Sensitivity of string compressors and repetitiveness measures
- Data compression via textual substitution
- On the Complexity of Finite Sequences
- Algorithms on Strings, Trees and Sequences
- Grammar-based codes: a new class of universal lossless source codes
- Deterministic sorting in O(nloglogn) time and linear space
- Optimal-Time Dictionary-Compressed Indexes
- Optimal rank and select queries on dictionary-compressed text
- At the roots of dictionary compression: string attractors
This page was built for publication: Substring complexities on run-length compressed strings