Efficient dualization of O( n)-term monotone disjunctive normal forms

Recommendations

Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
Computational aspects of monotone dualization: a brief survey
Left-to-right multiplication for monotone Boolean dualization
Self-duality of bounded monotone Boolean functions and related problems

Cites work

A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
A New Algorithm for Generating All the Maximal Independent Sets
A theory of diagnosis from first principles
An O(nm)-time algorithm for computing the dual of a regular Boolean function
An O(m n) algorithm for regular set-covering problems
Complexity of identification and dualization of positive Boolean functions
Design by example: An application of Armstrong relations
Dual subimplicants of positive Boolean functions
Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
Dualization of regular Boolean functions
Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
Fast learning of \(k\)-term DNF formulas with queries.
Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
How to assign votes in a distributed system
scientific article; zbMATH DE number 1354130 (Why is no real title available?)
scientific article; zbMATH DE number 2080451 (Why is no real title available?)
scientific article; zbMATH DE number 1754587 (Why is no real title available?)
Identifying the Minimal Transversals of a Hypergraph and Related Problems
Inferring minimal functional dependencies in Horn and q-Horn theories
On generating all maximal independent sets
On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
On the Complexity of Dualization of Monotone Disjunctive Normal Forms
Polynomial-time algorithms for regular set-covering and threshold synthesis
Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
Structure identification in relational data
The decision problem for some classes of sentences without quantifiers
The Maximum Latency and Identification of Positive Boolean Functions

Cited in

(14)

On the fractional chromatic number of monotone self-dual Boolean functions
On the frequency of the most frequently occurring variable in dual monotone DNFs
Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
Dual-bounded generating problems: Weighted transversals of a hypergraph
A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
scientific article; zbMATH DE number 169259 (Why is no real title available?)
A study on monotone self-dual Boolean functions
Left-to-right multiplication for monotone Boolean dualization
On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
A global parallel algorithm for the hypergraph transversal problem
Computational aspects of monotone dualization: a brief survey
On the complexity of monotone dualization and generating minimal hypergraph transversals
Self-duality of bounded monotone Boolean functions and related problems

This page was built for publication: Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms

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