Generating all maximal models of a Boolean expression

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)

zbMATH Keywords

computational complexity; maximal model generation; output-polynomial; transversal hypergraph

Mathematics Subject Classification ID

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