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

• A bisection algorithm for grammar-based compression of ordered trees
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A Universal Grammar-Based Code for Lossless Compression of Binary Trees
• 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
• 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?)
• 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 complexity of tree automata and XPath on grammar-compressed trees
• The Parallel Evaluation of General Arithmetic Expressions
• The Smallest Grammar Problem
• Tree compression with top trees
• Unification and matching on compressed terms
• Variations on the Common Subexpression Problem
• Weighted risk capital allocations

Cited in

(12)

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

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)