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 functionsformula size and depthlogarithmic lower bound on circuit depth
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (4)
On a relation between the depth and complexity of monotone Boolean formulas ⋮ ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO ⋮ On the depth complexity of formulas ⋮ Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths
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
This page was built for publication: Size-depth tradeoff in non-monotone Boolean formulae
