On a relation between the depth and complexity of monotone Boolean formulas

DOI10.33048/DAIO.2019.26.643MaRDI QIDQ5090140zbMATH OpenOpenAlexWikidataFDO

Authors I. S. Sergeev

Publication date 15 July 2022

Published in Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/da939

zbMATH Keywords

complexitymonotone functiondepthBoolean formula

Mathematics Subject Classification ID

Boolean functions (94D10)

Cites work

• scientific article; zbMATH DE number 3827757 (Why is no real title available?)
• scientific article; zbMATH DE number 4085569 (Why is no real title available?)
• scientific article; zbMATH DE number 3715454 (Why is no real title available?)
• scientific article; zbMATH DE number 1256664 (Why is no real title available?)
• Depth and polynomial equivalence of formulas for closed classes of two- valued logic
• Efficient Parallel Evaluation of Boolean Expressions
• On the Parallel Evaluation of Boolean Expressions
• On the depth complexity of formulas
• On the relation between depth and complexity of formulas in precomplete classes of \(k\)-valued logic
• Parallelizable algebras
• Reduction of Depth of Boolean Networks with a Fan-In Constraint
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• Sharpening an upper bound on the adder and comparator depths
• Size-depth tradeoff in monotone Boolean formulae
• Size-depth tradeoff in non-monotone Boolean formulae
• The Parallel Evaluation of Arithmetic Expressions Without Division
• The Parallel Evaluation of General Arithmetic Expressions
• The time required to evaluate division-free arithmetic expressions

Cited in

(2)

• Mathematical Foundations of Computer Science 2005
• Amplification of Bounded Depth Monotone Read-Once Boolean Formulae

This page was built for publication: On a relation between the depth and complexity of monotone Boolean formulas

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