Space-efficient SLP encoding for O( N)-time random access

DOI10.1007/S00224-025-10243-WMaRDI QIDQ7233479zbMATH OpenFDO

Authors Akito Takasaka, Tomohiro I

Publication date 27 April 2026

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-025-10243-W

zbMATH Keywords

data compressiongrammar compressionrandom access data structures

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Algorithms in computer science (68Wxx)

Cites work

• A space-optimal grammar compression
• A succinct grammar compression
• A universal algorithm for sequential data compression
• Access, rank, and select in grammar-compressed strings
• Algorithmics on SLP-compressed strings: a survey
• Balancing Straight-line Programs
• Compression by Contracting Straight-Line Programs
• Data structure lower bounds on random access to grammar-compressed strings
• Fully functional static and dynamic succinct trees
• Fully-Online Grammar Compression
• Log-logarithmic worst-case range queries are possible in space theta(N)
• On the Complexity of Finite Sequences
• Practical Random Access to SLP-Compressed Texts
• Random access to grammar-compressed strings and trees
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets

This page was built for publication: Space-efficient SLP encoding for \(O(\log N)\)-time random access

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