Approximation of grammar-based compression via recompression
DOI10.1016/J.TCS.2015.05.027zbMATH Open1330.68061OpenAlexW2119924552MaRDI QIDQ500975FDOQ500975
Authors: 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
Recommendations
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)
Cites Work
- A fully linear-time approximation algorithm for grammar-based compression
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- The complexity of compressed membership problems for finite automata
- Title not available (Why is that?)
- Approximation of smallest linear tree grammar
- Approximation of Grammar-Based Compression via Recompression
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- Algorithmics on SLP-compressed strings: a survey
- Title not available (Why is that?)
- Probability and Computing
- The Smallest Grammar Problem
- Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
- The macro model for data compression (extended abstract)
- On the Evaluation of Powers
- Efficient algorithms for Lempel-Ziv encoding
- Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
Cited In (34)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fully linear-time approximation algorithm for grammar-based compression
- Balancing straight-line programs for strings and trees
- Approximation of smallest linear tree grammar
- Constructing small tree grammars and small circuits for formulas
- An online algorithm for lightweight grammar-based compression
- Comparison of LZ77-type parsings
- Edit distance with block operations
- String Processing and Information Retrieval
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- A separation between RLSLPs and LZ77
- Document listing on repetitive collections with guaranteed performance
- Lyndon factorization of grammar compressed texts revisited
- A really simple approximation of smallest grammar
- A fully linear-time approximation algorithm for grammar-based compression
- Grammar-compressed indexes with logarithmic search time
- Compressibility of Finite Languages by Grammars
- Approximation of smallest linear tree grammar
- Quasi-distinct Parsing and Optimal Compression Methods
- A space-optimal grammar compression
- A \textit{really} simple approximation of smallest grammar
- Balancing run-length straight-line programs
- On the compressibility of finite languages and formal proofs
- Universal compressed text indexing
- Grammar-Based Compression in a Streaming Model
- Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings
- Rpair: rescaling RePair with Rsync
- A self-index on block trees
- Automata, Languages and Programming
- Computing all-vs-all MEMs in grammar-compressed text
- Tree compression using string grammars
- Reducing Simple Grammars: Exponential Against Highly-Polynomial Time in Practice
- Approximation of Grammar-Based Compression via Recompression
This page was built for publication: Approximation of grammar-based compression via recompression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q500975)
