Constructing small tree grammars and small circuits for formulas

摘要

It is shown that every tree of size n over a fixed set of a 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 0(((n·log m)/(log n)) and depth O(logn). 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).