Constructing small tree grammars and small circuits for formulas

It is shown that every tree of size n over a fixed set of σ different ranked symbols can be produced by a so called straight-line linear context-free tree grammar of size O(nlogσ⁡n), which can be used as a compressed representation of the input tree. Two algorithms for computing such tree grammar are presented: One working in logarithmic space and the other working in linear time. As a consequence, it is shown that every arithmetical formula of size n, in which only m≤n different variables occur, can be transformed (in linear time as well as in logspace) into an arithmetical circuit of size O(n⋅log⁡mlog⁡n) and depth O(log⁡n). 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).