View Related Documents

Abstract

In this paper, a new pre-processing step is proposed in the resolution of SAT instances, that recovers and exploits structural knowledge that is hidden in the CNF. It delivers an hybrid formula made of clauses together with a set of equations of the form y = f(x 1,..., x n ) where f is a standard connective operator among (∨, ∧, ⇔) and where y and x i are boolean variables of the initial SAT instance. This set of equations is then exploited to eliminate clauses and variables, while preserving satisfiability. These extraction and simplification techniques allowed us to implement a new SAT solver that proves to be the most efficient current one w.r.t. several important classes of instances.

Keywords  SAT - Boolean logic - propositional reasoning and search

Fulltext Preview

Image of the first page of the fulltext document