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 ( n log σ ⁡ 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 ⁡ m log ⁡ 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 ) . [ABSTRACT FROM AUTHOR]