Satisfiable formulas closed under replacement

MaRDI QIDQ2741513zbMATH OpenFDO

Authors Hans Kleine Büning, Xishun Zhao

Publication date 24 September 2001

zbMATH Keywords

propositional formulaslinear-time algorithm

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Combinatorial optimization (90C27)

Recommendations

• Generalizations of matched CNF formulas
• Two tractable subclasses of minimal unsatisfiable formulas
• The complexity of variable minimal formulas
• On Some SAT-Variants over Linear Formulas
• Complexity versus stability for classes of propositional formulas

Cites work

• A Computing Procedure for Quantification Theory
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• CNF-Satisfiability Test by Counting and Polynomial Average Time

Cited in

(7)

• The Helly property and satisfiability of Boolean formulas defined on set families
• New width parameters for SAT and \#SAT
• Are hitting formulas hard for resolution?
• Solving \#SAT using vertex covers
• Learning to assign degrees of belief in relational domains
• Generalizations of matched CNF formulas
• Community structure inspired algorithms for SAT and \#SAT

This page was built for publication: Satisfiable formulas closed under replacement

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