Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
From MaRDI portal
Publication:4337435
DOI10.1137/S0097539793269089zbMath0868.68095WikidataQ59560859 ScholiaQ59560859MaRDI QIDQ4337435
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)
Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Boolean programming (90C09)
Related Items (19)
Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ On algorithms for construction of all irreducible partial covers ⋮ On the fixed-parameter tractability of the equivalence test of monotone normal forms ⋮ Complete voting systems with two classes of voters: weightedness and counting ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ A geometric connection to threshold logic via cubical lattices ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Computational aspects of monotone dualization: a brief survey ⋮ Self-duality of bounded monotone Boolean functions and related problems ⋮ A study on monotone self-dual Boolean functions ⋮ Generating dual-bounded hypergraphs ⋮ Tree-shellability of Boolean functions ⋮ Guided inference of nested monotone Boolean functions ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ On the existence of a minimum integer representation for weighted voting systems ⋮ On the enumeration of Boolean functions with distinguished variables ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms ⋮ Almost all monotone Boolean functions are polynomially learnable using membership queries
This page was built for publication: Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
