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)

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

zbMATH Keywords

Boolean functionShannon functionstandard basisBoolean formulaalternationformula complexityhigh-accuracy asymptotic bounds

Mathematics Subject Classification ID

Boolean functions (06E30)

Cites Work

• Title not available (Why is that?)

Cited In (8)

• Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3
• Title not available (Why is that?)
• On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
• 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
• Refined bounds on Shannon's function for complexity of circuits of functional elements
• Title not available (Why is that?)

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)