zbMATH — the first resource for mathematics

Blocked clause elimination. (English) Zbl 1284.03208
Esparza, Javier (ed.) et al., Tools and algorithms for the construction and analysis of systems. 16th international conference, TACAS 2010, held as part of the joint European conferences on theory and practice of software, ETAPS 2010, Paphos, Cyprus, March 20–28, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-12001-5/pbk). Lecture Notes in Computer Science 6015, 129-144 (2010).
Summary: Boolean satisfiability (SAT) and its extensions are becoming a core technology for the analysis of systems. The SAT-based approach divides into three steps: encoding, preprocessing, and search. It is often argued that by encoding arbitrary Boolean formulas in conjunctive normal form (CNF), structural properties of the original problem are not reflected in the CNF. This should result in the fact that CNF-level preprocessing and SAT solver techniques have an inherent disadvantagecompared to related techniques applicable on the level of more structural SAT instance representations such as Boolean circuits. In this work we study the effect of a CNF-level simplification technique called blocked clause elimination (BCE). We show that BCE is surprisingly effective both in theory and in practice on CNFs resulting from a standard CNF encoding for circuits: without explicit knowledge of the underlying circuit structure, it achieves the same level of simplification as a combination of circuit-level simplifications and previously suggested polarity-based CNF encodings. Experimentally, we show that by applying BCE in preprocessing, further formula reduction and faster solving can be achieved, giving promise for applying BCE to speed up solvers.
For the entire collection see [Zbl 1185.68007].

03B70 Logic in computer science
03B05 Classical propositional logic
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI