Size-depth tradeoff in non-monotone Boolean formulae
From MaRDI portal
Publication:1132635
DOI10.1007/BF00264256zbMath0419.68083MaRDI QIDQ1132635
Jürgen Sattler, Beate Commentz-Walter
Publication date: 1980
Published in: Acta Informatica (Search for Journal in Brave)
complexity measures of Boolean functions; formula size and depth; logarithmic lower bound on circuit depth
68Q25: Analysis of algorithms and problem complexity
Related Items
On a relation between the depth and complexity of monotone Boolean formulas, ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO, Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths, On the depth complexity of formulas
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Komplexität von Entscheidungsproblemen. Ein Seminar
- Size-depth tradeoff in monotone Boolean formulae
- Efficient Parallel Evaluation of Boolean Expressions
- Restructuring of Arithmetic Expressions For Parallel Evaluation
- The Parallel Evaluation of General Arithmetic Expressions
- The Parallel Evaluation of Arithmetic Expressions Without Division
- Effect of the depth of formulas on their complexity