Approximation of smallest linear tree grammar
From MaRDI portal
Publication:342719
DOI10.1016/j.ic.2016.09.007zbMath1353.68154OpenAlexW2123297015MaRDI QIDQ342719
Publication date: 18 November 2016
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2016.09.007
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)
Related Items (3)
Compressed range minimum queries ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Slowing Down Top Trees for Better Worst-Case Compression
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- One-variable word equations in linear time
- XML compression via directed acyclic graphs
- A bisection algorithm for grammar-based compression of ordered trees
- Parameter reduction and automata evaluation for grammar-compressed trees
- Approximation of grammar-based compression via recompression
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- The complexity of tree automata and XPath on grammar-compressed trees
- A \textit{really} simple approximation of smallest grammar
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Tree compression using string grammars
- The complexity of compressed membership problems for finite automata
- Tree compression with top trees
- Constructing small tree grammars and small circuits for formulas
- A fully linear-time approximation algorithm for grammar-based compression
- Faster Fully Compressed Pattern Matching by Recompression
- Algorithmics on SLP-compressed strings: A survey
- Unification and matching on compressed terms
- Constructing Small Tree Grammars and Small Circuits for Formulas
- Congruence Closure of Compressed Terms in Polynomial Time
- Recompression
- The Smallest Grammar Problem
- Parallel Tree Contraction Part 2: Further Applications
- On the Complexity of Grammar-Based Compression over Fixed Alphabets
- Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
- Finding All Solutions of Equations in Free Groups and Monoids with Involution
- One-context Unification with STG-Compressed Terms is in NP
- Matching of Compressed Patterns with Character-Variables
- Context Unification is in PSPACE
- The macro model for data compression (Extended Abstract)
- Probability and Computing
This page was built for publication: Approximation of smallest linear tree grammar
