Generating all maximal models of a Boolean expression

DOI10.1016/S0020-0190(00)00023-5MaRDI QIDQ294760zbMATH OpenFDO

Authors Dimitris J. Kavvadias, Elias C. Stavropoulos, Martha Sideri

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitymaximal model generationoutput-polynomialtransversal hypergraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35)

Recommendations

• Compactly generating all satisfying truth assignments of a Horn formula
• On generating all solutions of generalized satisfiability problems
• On the complexity of the maximum satisfiability problem for Horn formulas
• The complexity of selecting maximal solutions
• Logic Programming

Cites work

• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1354130 (Why is no real title available?)
• An algorithm to compute circumscription
• Characterizing diagnoses and systems
• Horn functions and submodular Boolean functions
• How to assign votes in a distributed system
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Model-preference default theories
• NP-completeness: a retrospective
• On computing minimal models
• On generating all maximal independent sets
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Inverse Satisfiability Problem
• The complexity of model checking for circumscriptive formulae
• The complexity of satisfiability problems
• The complexity of selecting maximal solutions

Cited in

(16)

• Generating clause sequences of a CNF formula
• Compactly generating all satisfying truth assignments of a Horn formula
• Fast, flexible MUS enumeration
• A compact representation for minimizers of \(k\)-submodular functions
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• Minimal sets on propositional formulae. Problems and reductions
• On the counting complexity of propositional circumscription
• Translating between the representations of a ranked convex geometry
• Enumerating maximal consistent closed sets in closure systems
• A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)
• Resolution based algorithms for the transversal hypergraph generation problem
• Algorithms for \(k\)-meet-semidistributive lattices
• Dualization in lattices given by ordered sets of irreducibles
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• MCS Extraction with Sublinear Oracle Queries
• Redundancy in logic. II: 2CNF and Horn propositional formulae

This page was built for publication: Generating all maximal models of a Boolean expression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294760)