Electronic Resource
Springer
Theory of computing systems
13 (1979), S. 301-322
ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract The problem of minimizing the depth of formulas by equivalence preserving transformations is formalized in a general algebraic setting. For a particular algebraic system ∑0 specific methods of a dynamic programming nature are developed for proving lower bounds on depth. Such lower bounds for ∑0 automatically imply the same results for the systems of (i) arithmetic computations with addition and multiplication only, and (ii) computations over finite languages using union and concatenation. The specific lower bounds obtained are (i) depth 2n−o(n) for the permanent, (ii) depth (0.25+o(1))log2 n for the symmetric polynomials and (iii) depth 1.16logn for a problem of formula sizen.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01744302
Permalink
|
Location |
Call Number |
Expected |
Availability |