Constructing small tree grammars and small circuits for formulas

DOI10.1016/J.JCSS.2016.12.007zbMath1370.68061arXiv1407.4286OpenAlexW2963295241MaRDI QIDQ2396826

Moses Ganardi, Eric Noeth, Artur Jeż, Markus Lohrey, Danny Hucke

Publication date: 26 May 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.4286

zbMATH Keywords

tree compressiongrammar-based compressionarithmetical circuits over semirings

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 (5)

Approximation of smallest linear tree grammar ⋮ Size-optimal top dag compression ⋮ Tree compression using string grammars ⋮ Largest common prefix of a regular tree language ⋮ Unnamed Item

Uses Software

• TreeRePair

Cites Work

• 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
• Parameter reduction and automata evaluation for grammar-compressed trees
• Approximation of grammar-based compression via recompression
• A \textit{really} simple approximation of smallest grammar
• Tight lower bounds on the length of word chains
• On the length of word chains
• A note on word chains and regular languages
• Tree-size bounded alternation
• Size-depth tradeoffs for Boolean formulae
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Tree compression with top trees
• A fully linear-time approximation algorithm for grammar-based compression
• Succinct Representation of Balanced Parentheses and Static Trees
• Succinct Representations of Ordinal Trees
• Algorithmics on SLP-compressed strings: A survey
• Constructing Small Tree Grammars and Small Circuits for Formulas
• A Universal Grammar-Based Code for Lossless Compression of Binary Trees
• Compressing and indexing labeled trees, with applications
• The Smallest Grammar Problem
• Grammar-Based Compression in a Streaming Model
• Variations on the Common Subexpression Problem
• The Parallel Evaluation of General Arithmetic Expressions
• Least upper bounds on OBDD sizes
• Universal lossless compression via multilevel pattern matching
• Grammar-based codes: a new class of universal lossless source codes
• Size-Depth Tradeoffs for Algebraic Formulas
• Catalan Numbers
• Computational Complexity
• On the OBDD-representation of general Boolean functions

This page was built for publication: Constructing small tree grammars and small circuits for formulas