Replaceability and computational equivalence for monotone boolean functions

DOI10.1007/BF00288777zbMATH Open0545.94022MaRDI QIDQ798296FDOQ798296

Authors: Meurig Beynon 

Publication date: 1985

Published in: Acta Informatica (Search for Journal in Brave)

Recommendations

• The monotone circuit complexity of Boolean functions
• scientific article; zbMATH DE number 4204284
• The reduction of general Boolean functions to monotonic form
• On the planar monotone computation of Boolean functions
• Functions computed by monotone Boolean formulas with no repeated variables
• scientific article; zbMATH DE number 3884098
• Representations of monotone Boolean functions by linear programs
• Representations of monotone Boolean functions by linear programs
• Approximation of Boolean functions by monomial ones

zbMATH Keywords

finite distributive latticesabstract simplicial complexcomputational equivalencemonotone boolean function complexitymonotone boolean networksreplaceability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structure and representation theory of distributive lattices (06D05)

Cites Work

• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• Relating monotone formula size and monotone depth of Boolean functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Duality Theorems for Finitely Generated Vector Lattices
• Title not available (Why is that?)
• Vector lattices freely generated by distributive lattices

Cited In (2)

• Title not available (Why is that?)
• On the planar monotone computation of Boolean functions

This page was built for publication: Replaceability and computational equivalence for monotone boolean functions

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