Tree compression using string grammars
From MaRDI portal
Publication:1742370
DOI10.1007/s00453-017-0279-3zbMath1384.68016arXiv1504.05535OpenAlexW3155540153MaRDI QIDQ1742370
Eric Noeth, Moses Ganardi, Danny Hucke, Markus Lohrey
Publication date: 11 April 2018
Published in: Algorithmica, LATIN 2016: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.05535
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 (6)
Approximation of smallest linear tree grammar ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Tree compression using string grammars ⋮ Compressed range minimum queries ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- XML compression via directed acyclic graphs
- A bisection algorithm for grammar-based compression of ordered trees
- Ultra-succinct representation of ordered trees with applications
- Parameter reduction and automata evaluation for grammar-compressed trees
- Approximation of grammar-based compression via recompression
- Functional programs as compressed data
- Leaf languages and string compression
- Representing trees of higher degree
- The complexity of tree automata and XPath on grammar-compressed trees
- A \textit{really} simple approximation of smallest grammar
- The number of registers required for evaluating arithmetic expressions
- Nondeterministic \(NC^1\) computation
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Tree compression using string grammars
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Isomorphism of regular trees and words
- Tree compression with top trees
- Constructing small tree grammars and small circuits for formulas
- A fully linear-time approximation algorithm for grammar-based compression
- Succinct Representation of Balanced Parentheses and Static Trees
- Faster Fully Compressed Pattern Matching by Recompression
- Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
- Constructing Small Tree Grammars and Small Circuits for Formulas
- PP is as Hard as the Polynomial-Time Hierarchy
- Grammar-Based Tree Compression
- Compressing and indexing labeled trees, with applications
- The Smallest Grammar Problem
- On the Complexity of Numerical Analysis
- Random Access to Grammar-Compressed Strings and Trees
- A Brief History of Strahler Numbers
- The Compressed Word Problem for Groups
- Database Programming Languages
This page was built for publication: Tree compression using string grammars
