Balancing Straight Line Programs
We show that a context free grammar of size m 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 for w of size O(m) whose unique derivation tree has depth O(log n) 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 stated 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(log n) 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 (non commutative) semirings.A long version of the paper can be found in [1]
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)