Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle

DOI10.1137/S0097539793269089MaRDI QIDQ4337435zbMATH OpenWikidataFDO

Authors Endre Boros, Peter L. Hammer, Toshihide Ibaraki, Kazuhiko Kawakami

Publication date 3 August 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Boolean functionpolynomial-time algorithmsoracle

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09)

Recommendations

• A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
• A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
• A linear time algorithm for recognizing regular Boolean functions
• The Maximum Latency and Identification of Positive Boolean Functions

Cited in

(27)

• Self-duality of bounded monotone Boolean functions and related problems
• A geometric connection to threshold logic via cubical lattices
• On the fixed-parameter tractability of the equivalence test of monotone normal forms
• A study on monotone self-dual Boolean functions
• Tree-shellability of Boolean functions
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Generating dual-bounded hypergraphs
• Complexity of identification and dualization of positive Boolean functions
• Complete voting systems with two classes of voters: weightedness and counting
• Almost all monotone Boolean functions are polynomially learnable using membership queries
• Computational aspects of monotone dualization: a brief survey
• scientific article; zbMATH DE number 1522935 (Why is no real title available?)
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• A linear time algorithm for recognizing regular Boolean functions
• A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
• The Maximum Latency and Identification of Positive Boolean Functions
• On a convex geometric connection to threshold logic
• Generation of Boolean functions under the assumption of monotonicity
• On the enumeration of Boolean functions with distinguished variables
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• Enumerating minimal dominating sets in chordal bipartite graphs
• The splitting technique in monotone recognition
• Resolution based algorithms for the transversal hypergraph generation problem
• Guided inference of nested monotone Boolean functions
• On the existence of a minimum integer representation for weighted voting systems
• On algorithms for construction of all irreducible partial covers

This page was built for publication: Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle

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