Benjamin Kiesl, Martina Seidl, H. Tompits, Armin Biere,
"Blockedness in Propositional Logic: Are You Satisfied With Your Neighborhood?"
: Proc. 26th Intl. Joint Conf. on Artificial Intelligence (IJCAI'17), ijcai.org, Seite(n) 4884-4888, 2017
Original Titel:
Blockedness in Propositional Logic: Are You Satisfied With Your Neighborhood?
Sprache des Titels:
Englisch
Original Buchtitel:
Proc. 26th Intl. Joint Conf. on Artificial Intelligence (IJCAI'17)
Original Kurzfassung:
Clause-eliminationtechniquesthatsimplifyformulas by removing redundant clauses play an important role in modern SAT solving. Among the types of redundant clauses, blocked clauses are particularly popular. For checking whether a clause C is blocked in a formula F, one only needs to consider the so-called resolution neighborhood of C, i.e., the set of clauses that can be resolved with C. Because of this, blocked clauses are referred to as being locally redundant. In this paper, we discuss powerfulgeneralizationsofblockedclausesthatare still locally redundant, namely set-blocked clauses andsuper-blockedclauses. Wefurthermorepresent complexity results for deciding whether a clause is set-blocked or super-blocked.
Forschungs-