Size-depth tradeoff in monotone Boolean formulae
From MaRDI portal
Publication:1253236
DOI10.1007/BF00264580zbMath0395.94036OpenAlexW2082395645MaRDI QIDQ1253236
Publication date: 1979
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00264580
Boolean functionscomplexity measuresformula sizeswitching circuitsformula depthmonotone Boolean formulae
Complexity of computation (including implicit computational complexity) (03D15) Logical aspects of Boolean algebras (03G05)
Related Items
On a relation between the depth and complexity of monotone Boolean formulas ⋮ Bounds for parallel addition time of two numbers ⋮ Size-depth tradeoff in non-monotone Boolean formulae ⋮ Vertical processing of integer group-data streams. III: Application to binary arithmetic operations ⋮ Vertical processing of integer group-data streams. II: Application to binary arithmetic operations ⋮ 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
