Constructing small tree grammars and small circuits for formulas

DOI10.1016/J.JCSS.2016.12.007zbMATH Open1370.68061arXiv1407.4286OpenAlexW2963295241MaRDI QIDQ2396826FDOQ2396826

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)

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)$.

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

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

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)

Cites Work

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

Cited In (10)

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

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)