On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
From MaRDI portal
Publication:1961461
DOI10.1016/S0166-218X(99)00099-2zbMath0953.06013OpenAlexW1996070840MaRDI QIDQ1961461
Vladimir A. Gurvich, Leonid G. Khachiyan
Publication date: 14 February 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00099-2
NP-completenessdisjunctive normal formprime implicantmonotone Boolean functionconjunctive normal formprime implicatequasipolynomial time
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)
Related Items (39)
Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ Sequential testing of complex systems: a review ⋮ Generating all maximal models of a Boolean expression ⋮ Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data ⋮ An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation ⋮ Enumerating Prime Implicants of Propositional Formulae in Conjunctive Normal Form ⋮ Optimal resource allocation enables mathematical exploration of microbial metabolic configurations ⋮ On Dualization over Distributive Lattices ⋮ A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames ⋮ Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles ⋮ Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms ⋮ An inequality for polymatroid functions and its applications. ⋮ Discovering all associations in discrete data using frequent minimally infrequent attribute sets ⋮ On necessary and sufficient conditions for solvability of game forms. ⋮ On the readability of monotone Boolean formulae ⋮ Complexity of DNF minimization and isomorphism testing for monotone formulas ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Self-duality of bounded monotone Boolean functions and related problems ⋮ An improvement on the complexity of factoring read-once Boolean functions ⋮ Stability of two player game structures ⋮ Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden \(2 \times 2\) subgames ⋮ A structural characterization for certifying Robinsonian matrices ⋮ On fuzzy relational equations and the covering problem ⋮ Generating dual-bounded hypergraphs ⋮ Monotone bargaining is Nash-solvable ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ Isotone lattice-valued Boolean functions and cuts ⋮ On the complexity of the dualization problem ⋮ Unnamed Item ⋮ On the relation between fuzzy max-Archimedean t-norm relational equations and the covering problem ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Monotone Boolean dualization is in co-NP\([\log^{2}n\).] ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms ⋮ On Quantifying Literals in Boolean Logic and its Applications to Explainable AI
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorial characterization of read-once formulae
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Random generation of combinatorial structures from a uniform distribution
- Dualization of regular Boolean functions
- On generating all maximal independent sets
- An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
- Complexity of identification and dualization of positive Boolean functions
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Dual subimplicants of positive Boolean functions
This page was built for publication: On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
