Constructing small tree grammars and small circuits for formulas

DOI10.1016/J.JCSS.2016.12.007MaRDI QIDQ2396826zbMATH OpenOpenAlexFDO

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

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, https://drops.dagstuhl.de/opus/volltexte/2014/4863/

zbMATH Keywords

tree compressiongrammar-based compressionarithmetical circuits over semirings

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)

Abstract: It is shown that every tree of size $n$ over a fixed set of $sigma$ different ranked symbols can be decomposed (in linear time as well as in logspace) into $$ many hierarchically defined pieces. Formally, such a hierarchical decomposition has the form of a straight-line linear context-free tree grammar of size $$, which can be used as a compressed representation of the input tree. This generalizes an analogous result for strings. Previous grammar-based tree compressors were not analyzed for the worst-case size of the computed grammar, except for the top dag of Bille et al., for which only the weaker upper bound of $$ (which was very recently improved to $$ by H"ubschle-Schneider and Raman) for unranked and unlabelled trees has been derived. The main result is used to show that every arithmetical formula of size $n$, in which only $mleqn$ different variables occur, can be transformed (in linear time as well as in logspace) into an arithmetical circuit of size $$ and depth $O(logn)$. This refines a classical result of Brent from 1974, according to which an arithmetical formula of size $n$ can be transformed into a logarithmic depth circuit of size $O(n)$.

Recommendations

• Constructing small tree grammars and small circuits for formulas
• Interactive construction of small grammars
• Approximation of smallest linear tree grammar
• Approximation of smallest linear tree grammar
• A really simple approximation of smallest grammar
• A \textit{really} simple approximation of smallest grammar
• scientific article; zbMATH DE number 1456950
• Context-free grammars on trees
• Publication:4502802
• Minimal equational representations of recognizable tree languages

Cites work

• scientific article; zbMATH DE number 177816 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A Universal Grammar-Based Code for Lossless Compression of Binary Trees
• A \textit{really} simple approximation of smallest grammar
• A bisection algorithm for grammar-based compression of ordered trees
• A fully linear-time approximation algorithm for grammar-based compression
• A note on word chains and regular languages
• Algorithmics on SLP-compressed strings: a survey
• Analytic combinatorics
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximation of grammar-based compression via recompression
• Approximation of smallest linear tree grammar
• Catalan Numbers
• Compressing and indexing labeled trees, with applications
• Computational Complexity
• Constructing small tree grammars and small circuits for formulas
• Grammar-Based Compression in a Streaming Model
• Grammar-based codes: a new class of universal lossless source codes
• Least upper bounds on OBDD sizes
• On the OBDD-representation of general Boolean functions
• On the length of word chains
• Parameter reduction and automata evaluation for grammar-compressed trees
• Size-Depth Tradeoffs for Algebraic Formulas
• Size-depth tradeoffs for Boolean formulae
• Succinct representation of balanced parentheses and static trees
• Succinct representations of ordinal trees
• The Parallel Evaluation of General Arithmetic Expressions
• The Smallest Grammar Problem
• Tight lower bounds on the length of word chains
• Tree compression with top trees
• Tree-size bounded alternation
• Universal lossless compression via multilevel pattern matching
• Variations on the Common Subexpression Problem
• XML compression via directed acyclic graphs

Cited in

(9)

• Computing Tiny Clause Normal Forms
• A unified method for placing problems in polylogarithmic depth
• Interactive construction of small grammars
• Approximation of smallest linear tree grammar
• Balancing Straight-line Programs
• Size-optimal top dag compression
• Constructing small tree grammars and small circuits for formulas
• Largest common prefix of a regular tree language
• A universal tree balancing theorem

Describes a project that uses

Uses Software

• TreeRePair

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

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