Balancing Straight-line Programs
Open Access
- 30 June 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (4), 1-40
- https://doi.org/10.1145/3457389
Abstract
We show that a context-free grammar of size that produces a single string of length (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for of size , whose unique derivation tree has depth . This solves an open problem in the area of grammar-based compression, improves many results in this area, and greatly simplifies many existing constructions. Similar results are shown for two formalisms for grammar-based tree compression: top dags and forest straight-line programs. These balancing results can be all deduced from a single meta-theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to with the cost of a constant multiplicative size increase. Here, refers to the size of the unfolding (or unravelling) of the circuit. In particular, this results applies to standard arithmetic circuits over (noncommutative) semirings.Keywords
Funding Information
- National Science Centre, Poland (2017/26/E/ST6/00191)
- DFG research project (LO 748/10-1)
This publication has 33 references indexed in Scilit:
- Data Structure Lower Bounds on Random Access to Grammar-Compressed StringsLecture Notes in Computer Science, 2013
- Algorithmics on SLP-compressed strings: A surveyGroups - Complexity - Cryptology, 2012
- Efficient memory representation of XML document treesInformation Systems, 2008
- The Smallest Grammar ProblemIEEE Transactions on Information Theory, 2005
- Application of Lempel–Ziv factorization to the approximation of grammar-based compressionTheoretical Computer Science, 2003
- Non-commutative arithmetic circuits: depth reduction and size lower boundsTheoretical Computer Science, 1998
- Surpassing the information theoretic bound with fusion treesJournal of Computer and System Sciences, 1993
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic timeAlgorithmica, 1988
- Fast Parallel Computation of Polynomials Using Few ProcessorsSIAM Journal on Computing, 1983
- Circuit size is nonlinear in depthTheoretical Computer Science, 1976