Approximation of smallest linear tree grammar

DOI10.1016/J.IC.2016.09.007MaRDI QIDQ342719zbMATHOpenAlexFDO

Authors 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)

Recommendations

• Approximation of smallest linear tree grammar
• Approximation of grammar-based compression via recompression
• Approximation of Grammar-Based Compression via Recompression
• String Processing and Information Retrieval
• A fully linear-time approximation algorithm for grammar-based compression

Cites work

• scientific article; zbMATH DE number 5872386 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1149447 (Why is no real title available?)
• A \textit{really} simple approximation of smallest grammar
• A bisection algorithm for grammar-based compression of ordered trees
• A fully linear-time approximation algorithm for grammar-based compression
• 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
• Congruence closure of compressed terms in polynomial time
• Constructing small tree grammars and small circuits for formulas
• Constructing small tree grammars and small circuits for formulas
• Context unification is in PSPACE
• Finding All Solutions of Equations in Free Groups and Monoids with Involution
• Introduction to algorithms.
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• Matching of compressed patterns with character-variables
• On the complexity of grammar-based compression over fixed alphabets
• One-context unification with STG-compressed terms is in NP
• One-variable word equations in linear time
• Parallel Tree Contraction Part 2: Further Applications
• Parameter reduction and automata evaluation for grammar-compressed trees
• Probability and Computing
• Recompression: a simple and powerful technique for word equations
• Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
• The Smallest Grammar Problem
• The complexity of compressed membership problems for finite automata
• The complexity of tree automata and XPath on grammar-compressed trees
• The macro model for data compression (extended abstract)
• Tree compression with top trees
• Unification and matching on compressed terms
• XML compression via directed acyclic graphs

Cited in

(9)

• Slowing down top trees for better worst-case compression
• Parameter Reduction in Grammar-Compressed Trees
• Constant delay traversal of grammar-compressed graphs with bounded rank
• Slowing down top trees for better worst-case compression
• Approximation of smallest linear tree grammar
• A bisection algorithm for grammar-based compression of ordered trees
• Constructing small tree grammars and small circuits for formulas
• Constructing small tree grammars and small circuits for formulas
• Regular Approximation of Weighted Linear Context-Free Tree Languages

Describes a project that uses

Uses Software

• TreeRePair

This page was built for publication: Approximation of smallest linear tree grammar

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