Approximation of smallest linear tree grammar

DOI10.1016/j.ic.2016.09.007zbMath1353.68154OpenAlexW2123297015MaRDI QIDQ342719

Artur Jeż, Markus Lohrey

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

zbMATH Keywords

tree compressiongrammar-based compressiontree grammars

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)

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

• TreeRePair

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