Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
From MaRDI portal
Publication:1861581
DOI10.1016/S0166-218X(02)00204-4zbMath1011.06015MaRDI QIDQ1861581
Publication date: 9 March 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
hypergraphcombinatorial enumerationdualizationmonotone Boolean functionpolynomial total time algorithmtransversal computation\(k\)-term DNF
Related Items
Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ A global parallel algorithm for the hypergraph transversal problem ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ 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 ⋮ A study on monotone self-dual Boolean functions ⋮ On the fractional chromatic number of monotone self-dual Boolean functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Design by example: An application of Armstrong relations
- Fast learning of \(k\)-term DNF formulas with queries.
- Dualization of regular Boolean functions
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- An O(m n) algorithm for regular set-covering problems
- A theory of diagnosis from first principles
- On generating all maximal independent sets
- Structure identification in relational data
- An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
- Inferring minimal functional dependencies in Horn and q-Horn theories
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Complexity of identification and dualization of positive Boolean functions
- Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- A New Algorithm for Generating All the Maximal Independent Sets
- Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
- The Maximum Latency and Identification of Positive Boolean Functions
- A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Dual subimplicants of positive Boolean functions
- The decision problem for some classes of sentences without quantifiers
This page was built for publication: Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
