Approximation of grammar-based compression via recompression

DOI10.1016/j.tcs.2015.05.027zbMath1330.68061OpenAlexW2119924552MaRDI QIDQ500975

Artur Jeż

Publication date: 8 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.05.027

zbMATH Keywords

grammar-based compressionsmallest grammar

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Related Items (14)

Comparison of LZ77-type parsings ⋮ A separation between RLSLPs and LZ77 ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Approximation of smallest linear tree grammar ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Balancing run-length straight-line programs ⋮ A \textit{really} simple approximation of smallest grammar ⋮ Unnamed Item ⋮ On the compressibility of finite languages and formal proofs ⋮ Universal compressed text indexing ⋮ A Self-index on Block Trees ⋮ Tree compression using string grammars ⋮ Balancing straight-line programs for strings and trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• The complexity of compressed membership problems for finite automata
• A fully linear-time approximation algorithm for grammar-based compression
• Faster Fully Compressed Pattern Matching by Recompression
• Algorithmics on SLP-compressed strings: A survey
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• The Smallest Grammar Problem
• On the Evaluation of Powers
• Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
• Approximation of Grammar-Based Compression via Recompression
• Efficient algorithms for Lempel-Ziv encoding
• The macro model for data compression (Extended Abstract)
• Probability and Computing

This page was built for publication: Approximation of grammar-based compression via recompression