On the synthesis and complexity of formulae with bounded depth of alternation

DOI10.3103/S0278641912020021zbMATH Open1258.94054MaRDI QIDQ1759151FDOQ1759151

Authors Xianqiang Yang 

Publication date 20 November 2012

Published in Moscow University Computational Mathematics and Cybernetics (Search for Journal in Brave)

zbMATH Keywords

Boolean functionShannon functionstandard basisBoolean formulaalternationformula complexityhigh-accuracy asymptotic bounds

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
• Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3
• scientific article; zbMATH DE number 3841817
• Synthesis of formulas whose depth and complexity do not exceed asymptotically the best estimates of high accuracy
• scientific article; zbMATH DE number 4085724

Cited in

(8)

• The average sensitivity of bounded-depth formulas
• A finite alternation result for reversible Boolean circuits
• Synthesis of formulas whose depth and complexity do not exceed asymptotically the best estimates of high accuracy
• scientific article; zbMATH DE number 3841817 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 5827847 (Why is no real title available?)
• Refined bounds on Shannon's function for complexity of circuits of functional elements

This page was built for publication: On the synthesis and complexity of formulae with bounded depth of alternation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759151)