Grammar-Based Tree Compression

DOI10.1007/978-3-319-21500-6_3zbMath1434.68130OpenAlexW1754942486MaRDI QIDQ3451087

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

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

Related Items (9)

On stricter reachable repetitiveness measures ⋮ Size-optimal top dag compression ⋮ Tree compression using string grammars ⋮ Grammar-based compression of unranked trees ⋮ Inter-procedural Two-Variable Herbrand Equalities ⋮ Compressed range minimum queries ⋮ Learning from Łukasiewicz and Meredith: investigations into proof structures ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Balancing straight-line programs for strings and trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A bisection algorithm for grammar-based compression of ordered trees
• Parameter reduction and automata evaluation for grammar-compressed trees
• Functional programs as compressed data
• The complexity of tree automata and XPath on grammar-compressed trees
• Weighted risk capital allocations
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Isomorphism of regular trees and words
• Algorithmics on SLP-compressed strings: A survey
• Unification and matching on compressed terms
• Constructing Small Tree Grammars and Small Circuits for Formulas
• A Universal Grammar-Based Code for Lossless Compression of Binary Trees
• Congruence Closure of Compressed Terms in Polynomial Time
• Compressed Tree Canonization
• The Smallest Grammar Problem
• The Complexity of Monadic Second-Order Unification
• Variations on the Common Subexpression Problem
• The Parallel Evaluation of General Arithmetic Expressions
• Grammar-based codes: a new class of universal lossless source codes
• Approximation of Grammar-Based Compression via Recompression
• One-context Unification with STG-Compressed Terms is in NP
• Matching of Compressed Patterns with Character-Variables
• Tree Compression with Top Trees

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