Balancing straight-line programs for strings and trees

DOI10.1007/978-3-030-51466-2_26MaRDI QIDQ2106614zbMATH OpenOpenAlexFDO

Authors Markus Lohrey

Publication date 16 December 2022

Full work available at URL https://doi.org/10.1007/978-3-030-51466-2_26

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Balancing Straight-line Programs
• Straight-line programs: a practical test (extended abstract)
• Approximation of smallest linear tree grammar

Cites work

• A \textit{really} simple approximation of smallest grammar
• Access, rank, and select in grammar-compressed strings
• Algorithmics on SLP-compressed strings: a survey
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximation of grammar-based compression via recompression
• Balancing Straight-line Programs
• Constant-time tree traversal and subtree equality check for grammar-compressed trees
• Database Programming Languages
• Detecting regularities on grammar-compressed strings
• Grammar-Based Tree Compression
• Random access to grammar-compressed strings and trees
• Slowing down top trees for better worst-case compression
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• The Smallest Grammar Problem
• Tight bounds for top tree compression
• Tree compression with top trees

This page was built for publication: Balancing straight-line programs for strings and trees

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