Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
type: Item
instance of: scholarly article
title: Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
zbMATH Open document ID: 1011.06015
DOI: 10.1016/S0166-218X(02)00204-4
author: Kazuhisa Makino
published in: Discrete Applied Mathematics
publication date: 2003-03-09T00:00:00Z
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 1878541
zbMATH Keywords: dualization
zbMATH Keywords: monotone Boolean function
zbMATH Keywords: \(k\)-term DNF
zbMATH Keywords: hypergraph
zbMATH Keywords: transversal computation
zbMATH Keywords: combinatorial enumeration
zbMATH Keywords: polynomial total time algorithm
MaRDI profile type: Publication
cites work: An O(m n) algorithm for regular set-covering problems
cites work: Complexity of identification and dualization of positive Boolean functions
cites work: Fast learning of \(k\)-term DNF formulas with queries.
cites work: Dual subimplicants of positive Boolean functions
cites work: Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
cites work: Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
cites work: Dualization of regular Boolean functions
cites work: Structure identification in relational data
cites work: Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
cites work: How to assign votes in a distributed system
cites work: On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
cites work: Inferring minimal functional dependencies in Horn and q-Horn theories
cites work: On generating all maximal independent sets
cites work: Q4268444
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: The Maximum Latency and Identification of Positive Boolean Functions
cites work: A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
cites work: Design by example: An application of Armstrong relations
cites work: The decision problem for some classes of sentences without quantifiers
cites work: Polynomial-time algorithms for regular set-covering and threshold synthesis
cites work: An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
cites work: A theory of diagnosis from first principles
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: Q4535012
cites work: Q4473243
description: scientific article; zbMATH DE number 1878541