Balancing Straight-line Programs.

We show that a context-free grammar of sizem that produces a single string w of length n (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar forw of size O(m), whose unique derivation tree has depth O(logn). 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 O(logn) with the cost of a constant multiplicative size increase. Here, n refers to the size of the unfolding (or unravelling) of the circuit. In particular, this results applies to standard arithmetic circuits over (noncommutative) semirings. [ABSTRACT FROM AUTHOR]