Balancing run-length straight-line programs

DOI10.1007/978-3-031-20643-6_9zbMath1525.68208arXiv2206.13027OpenAlexW4312968505MaRDI QIDQ6111582

Cristian Urbina, Gonzalo Navarro, Francisco Olivares

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/2206.13027

zbMATH Keywords

repetitive stringsrun-length straight-line programssubstring range problems

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation of grammar-based compression via recompression
• Faster entropy-bounded compressed suffix trees
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Fingerprints in compressed strings
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• The Smallest Grammar Problem
• Efficient randomized pattern-matching algorithms
• On the Complexity of Finite Sequences
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
• Optimal-Time Dictionary-Compressed Indexes
• Balancing Straight-line Programs
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• At the roots of dictionary compression: string attractors
• Random Access to Grammar-Compressed Strings and Trees

This page was built for publication: Balancing run-length straight-line programs