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

DOI10.1137/S0097539793269089zbMATH Open0868.68095WikidataQ59560859 ScholiaQ59560859MaRDI QIDQ4337435FDOQ4337435

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

Publication date: 3 August 1997

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

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

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)

Cited In (25)

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

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)