On the Complexity of Dualization of Monotone Disjunctive Normal Forms
From MaRDI portal
Publication:3837390
DOI10.1006/jagm.1996.0062zbMath0864.68038OpenAlexW2080947358MaRDI QIDQ3837390
Michael L. Fredman, Leonid G. Khachiyan
Publication date: 8 December 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/cf09761a7a863915f91346881df95484b5bee617
Related Items
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ Fast, flexible MUS enumeration ⋮ Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ Sequential testing of complex systems: a review ⋮ On the complexity of inducing categorical and quantitative association rules ⋮ A note on systems with max-min and max-product constraints ⋮ Pareto-optimal patterns in logical analysis of data ⋮ 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 ⋮ Cooperation through social influence ⋮ Minimum implicational basis for \(\wedge\)-semidistributive lattices ⋮ A global parallel algorithm for the hypergraph transversal problem ⋮ Extended dualization: application to maximal pattern mining ⋮ On the fixed-parameter tractability of the equivalence test of monotone normal forms ⋮ On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs ⋮ On the frequency of the most frequently occurring variable in dual monotone DNFs ⋮ Factoring Boolean functions using graph partitioning ⋮ Density condensation of Boolean formulas ⋮ An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation ⋮ Lattices, closures systems and implication bases: a survey of structural aspects and algorithms ⋮ A max-term counting based knowledge inconsistency checking strategy and inconsistency measure calculation of fuzzy knowledge based systems ⋮ Intersecting restrictions in clutters ⋮ On the Boolean connectivity problem for Horn relations ⋮ Optimal resource allocation enables mathematical exploration of microbial metabolic configurations ⋮ Understanding the complexity of axiom pinpointing in lightweight description logics ⋮ Multivariate value at risk and related topics ⋮ On a cone covering problem ⋮ Monotone dualization problem and its generalizations: asymptotic estimates of the number of solutions ⋮ Total tightness implies Nash-solvability for three-person game forms ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Forms of representation for simple games: sizes, conversions and equivalences ⋮ On the complexity of enumerating pseudo-intents ⋮ One approach to decoding monotone logical function ⋮ Interior and exterior functions of positive Boolean functions. ⋮ An inequality for polymatroid functions and its applications. ⋮ Inverse subsumption for complete explanatory induction ⋮ Discovering all associations in discrete data using frequent minimally infrequent attribute sets ⋮ Nash-solvable two-person symmetric cycle game forms ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ On necessary and sufficient conditions for solvability of game forms. ⋮ Bidual Horn functions and extensions ⋮ Minimum self-dual decompositions of positive dual-minor Boolean functions ⋮ On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions ⋮ Inner-core and outer-core functions of partially defined Boolean functions ⋮ Efficient algorithms for dualizing large-scale hypergraphs ⋮ Generating cut conjunctions in graphs and related problems ⋮ Dualization problem over the product of chains: asymptotic estimates for the number of solutions ⋮ Separable discrete functions: recognition and sufficient conditions ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Complexity of DNF minimization and isomorphism testing for monotone formulas ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ 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 ⋮ Stability of two player game structures ⋮ Discovery of the \(D\)-basis in binary tables based on hypergraph dualization ⋮ Dualization in lattices given by ordered sets of irreducibles ⋮ RQL: a query language for rule discovery in databases ⋮ Algorithms for \(k\)-meet-semidistributive lattices ⋮ Complexity of simplicial homology and independence complexes of chordal graphs ⋮ On enumerating minimal dicuts and strongly connected subgraphs ⋮ An algebraic algorithm for solving parametric integer programs ⋮ Fast algorithms for implication bases and attribute exploration using proper premises ⋮ A study on monotone self-dual Boolean functions ⋮ 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 the counting complexity of propositional circumscription ⋮ Acyclic, or totally tight, two-person game forms: characterization and main properties ⋮ Tropical polar cones, hypergraph transversals, and mean payoff games ⋮ Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Maximal sensitivity of Boolean nested canalizing functions ⋮ Incremental delay enumeration: space and time ⋮ On the dualization in distributive lattices and related problems ⋮ Translating between the representations of a ranked convex geometry ⋮ On the logical analysis of partially ordered data in the supervised classification problem ⋮ Masking patterns in sequences: A new class of motif discovery with don't cares ⋮ Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games ⋮ Translation among CNFs, characteristic models and ordered binary decision diagrams ⋮ Sensitivities and block sensitivities of elementary symmetric Boolean functions ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ On Maximal Chain Subgraphs and Covers of Bipartite Graphs ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs ⋮ Lower bounds for three algorithms for transversal hypergraph generation ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Finding maximal independent elements of products of partial orders (the case of chains) ⋮ Minimal and locally minimal games and game forms ⋮ Certificate complexity of elementary symmetric Boolean functions ⋮ Recognition and dualization of disguised bidual Horn functions. ⋮ Monotone Boolean dualization is in co-NP\([\log^{2}n\).] ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms ⋮ Asymptotically optimal dualization algorithms ⋮ Version spaces and the consistency problem ⋮ An average study of hypergraphs and their minimal transversals ⋮ Enumerating maximal consistent closed sets in closure systems ⋮ On Tackling Explanation Redundancy in Decision Trees ⋮ NP-completeness: A retrospective ⋮ On Dualization over Distributive Lattices ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ 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 ⋮ Controlling entity integrity with key sets ⋮ Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms ⋮ Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements ⋮ Social disruption games in signed networks ⋮ Counting Minimal Dominating Sets ⋮ Enumerating Minimal Hypotheses and Dualizing Monotone Boolean Functions on Lattices ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ How to Apply SAT-Solving for the Equivalence Test of Monotone Normal Forms ⋮ Monotone term decision lists ⋮ Generating dual-bounded hypergraphs ⋮ Unnamed Item ⋮ Tree-shellability of Boolean functions ⋮ Dualization in lattices given by implicational bases ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Enumeration of Minimal Dominating Sets and Variants ⋮ Generating all vertices of a polyhedron is hard ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction ⋮ Unnamed Item ⋮ On the Complexity of the Decisive Problem in Simple and Weighted Games ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Unnamed Item ⋮ Measuring the Implications of the D-Basis in Analysis of Data in Biomedical Studies ⋮ Stoichiometric and Constraint-Based Analysis of Biochemical Reaction Networks ⋮ On Quantifying Literals in Boolean Logic and its Applications to Explainable AI
