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)

Full work available at URL https://doi.org/10.1137/S0097539793269089

zbMATH Keywords

Boolean functionoraclepolynomial-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) 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

(30)

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

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)