1. Constructing small tree grammars and small circuits for formulas.
- Author
-
Ganardi, Moses, Hucke, Danny, Jeż, Artur, Lohrey, Markus, and Noeth, Eric
- Subjects
- *
QUANTUM computing , *ALGORITHMS , *ELECTRIC circuits , *ARITHMETICAL algebraic geometry , *DATA compression - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF