Generating all maximal models of a Boolean expression
From MaRDI portal
Publication:294760
DOI10.1016/S0020-0190(00)00023-5zbMath1339.03015MaRDI QIDQ294760
Elias C. Stavropoulos, Dimitris J. Kavvadias, Martha Sideris
Publication date: 16 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
03B35: Mechanization of proofs and logical operations
Related Items
Dualization in lattices given by implicational bases, Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements, Fast, flexible MUS enumeration, Dualization in lattices given by ordered sets of irreducibles, Algorithms for \(k\)-meet-semidistributive lattices, On the counting complexity of propositional circumscription, A compact representation for minimizers of \(k\)-submodular functions, Minimal sets on propositional formulae. Problems and reductions, Monotone Boolean dualization is in co-NP\([\log^{2}n\).], Translating between the representations of a ranked convex geometry, Enumerating maximal consistent closed sets in closure systems, Resolution based algorithms for the transversal hypergraph generation problem, Redundancy in logic. II: 2CNF and Horn propositional formulae, MCS Extraction with Sublinear Oracle Queries, A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On generating all maximal independent sets
- An algorithm to compute circumscription
- Characterizing diagnoses and systems
- The complexity of model checking for circumscriptive formulae
- On computing minimal models
- Horn functions and submodular Boolean functions
- The complexity of selecting maximal solutions
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Model-preference default theories
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- The Inverse Satisfiability Problem
- NP-completeness: A retrospective
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- The complexity of satisfiability problems