Grammar-Based Tree Compression

DOI10.1007/978-3-319-21500-6_3MaRDI QIDQ3451087zbMATH OpenOpenAlexFDO

Authors Markus Lohrey

Publication date 10 November 2015

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://infoscience.epfl.ch/record/52615/files/IC_TECH_REPORT_200480.pdf

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Cites work

• scientific article; zbMATH DE number 1722707 (Why is no real title available?)
• scientific article; zbMATH DE number 177816 (Why is no real title available?)
• scientific article; zbMATH DE number 1003252 (Why is no real title available?)
• A Universal Grammar-Based Code for Lossless Compression of Binary Trees
• A bisection algorithm for grammar-based compression of ordered trees
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Algorithmics on SLP-compressed strings: a survey
• Approximation of Grammar-Based Compression via Recompression
• Approximation of smallest linear tree grammar
• Compressed tree canonization
• Congruence closure of compressed terms in polynomial time
• Constructing small tree grammars and small circuits for formulas
• Functional programs as compressed data
• Grammar-based codes: a new class of universal lossless source codes
• Isomorphism of regular trees and words
• Linear compressed pattern matching for polynomial rewriting (extended abstract)
• Matching of compressed patterns with character-variables
• One-context unification with STG-compressed terms is in NP
• Parameter reduction and automata evaluation for grammar-compressed trees
• The Complexity of Monadic Second-Order Unification
• The Parallel Evaluation of General Arithmetic Expressions
• The Smallest Grammar Problem
• The complexity of tree automata and XPath on grammar-compressed trees
• Tree compression with top trees
• Unification and matching on compressed terms
• Variations on the Common Subexpression Problem
• Weighted risk capital allocations

Cited in

(11)

• Balancing straight-line programs for strings and trees
• Parameter reduction and automata evaluation for grammar-compressed trees
• scientific article; zbMATH DE number 7360256 (Why is no real title available?)
• Leaf languages and string compression
• Algorithmic Compression of Finite Tree Languages by Rigid Acyclic Grammars
• On stricter reachable repetitiveness measures
• Learning from Łukasiewicz and Meredith: investigations into proof structures
• Constant delay traversal of grammar-compressed graphs with bounded rank
• Investigations into proof structures
• Size-optimal top dag compression
• Grammar-Based Compression in a Streaming Model

This page was built for publication: Grammar-Based Tree Compression

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