On the planar monotone computation of Boolean functions

DOI10.1016/0304-3975(87)90068-5MaRDI QIDQ1099134zbMATH OpenOpenAlexFDO

Authors Meurig Beynon, John Buckle

Publication date 1987

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(87)90068-5

zbMATH Keywords

clausesmonotone Boolean functionplanar monotone circuitplanar monotone computableprime implicants

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4172377
• scientific article; zbMATH DE number 3906395
• On the complexity of planar Boolean circuits
• Functions computed by monotone Boolean formulas with no repeated variables
• On monotone simulations on nonmonotone networks

Cites work

• scientific article; zbMATH DE number 3884098 (Why is no real title available?)
• scientific article; zbMATH DE number 3906395 (Why is no real title available?)
• Replaceability and computational equivalence for monotone boolean functions

Cited in

(14)

• On the complexity of planar Boolean circuits
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Succinct certification of monotone circuits
• Computing with planar toppling domino arrangements
• Order of power of planar circuits implementing Boolean functions
• Computing with planar toppling domino arrangements
• scientific article; zbMATH DE number 4172377 (Why is no real title available?)
• On Planar Boolean CSP
• scientific article; zbMATH DE number 3906395 (Why is no real title available?)
• scientific article; zbMATH DE number 1129493 (Why is no real title available?)
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Evaluating Monotone Circuits on Cylinders, Planes and Tori
• Planar acyclic computation
• Replaceability and computational equivalence for monotone boolean functions

This page was built for publication: On the planar monotone computation of Boolean functions

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