On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions

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

zbMATH Keywords

NP-completeness disjunctive normal form prime implicant monotone Boolean function conjunctive normal form prime implicate quasipolynomial time

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items

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