On the synthesis and complexity of formulae with bounded depth of alternation
From MaRDI portal
Publication:1759151
DOI10.3103/S0278641912020021zbMath1258.94054MaRDI QIDQ1759151
Publication date: 20 November 2012
Published in: Moscow University Computational Mathematics and Cybernetics (Search for Journal in Brave)
Boolean functionalternationformula complexityShannon functionstandard basisBoolean formulahigh-accuracy asymptotic bounds
Related Items (3)
Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3 ⋮ On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates ⋮ Refined bounds on Shannon's function for complexity of circuits of functional elements
Cites Work
This page was built for publication: On the synthesis and complexity of formulae with bounded depth of alternation
