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

DOI10.33048/DAIO.2019.26.643zbMATH Open1492.94258OpenAlexW4240586718WikidataQ126356967 ScholiaQ126356967MaRDI QIDQ5090140FDOQ5090140

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

• Depth and polynomial equivalence of formulas for closed classes of two- valued logic
• On the relation between depth and complexity of formulas in precomplete classes of \(k\)-valued logic
• Parallelizable algebras
• Title not available (Why is that?)
• On the depth complexity of formulas
• Title not available (Why is that?)
• The Parallel Evaluation of General Arithmetic Expressions
• Sharpening an upper bound on the adder and comparator depths
• Size-depth tradeoff in monotone Boolean formulae
• Title not available (Why is that?)
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• The Parallel Evaluation of Arithmetic Expressions Without Division
• Title not available (Why is that?)
• Size-depth tradeoff in non-monotone Boolean formulae
• Efficient Parallel Evaluation of Boolean Expressions
• The time required to evaluate division-free arithmetic expressions
• Reduction of Depth of Boolean Networks with a Fan-In Constraint
• On the Parallel Evaluation of Boolean 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)