Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Computing prime implicants

Abstract : Model checking and counter-example guided abstraction refinement are examples of applications of SAT solving requiring the production of models for satisfiable formulas. Better than giving a truth value to every variable, one can provide an implicant, i.e. a partial assignment of the variables such that every full extension is a model for the formula. An implicant is prime if every assignment is necessary. Since prime implicants contain no literal irrelevant for the satisfiability of the formula, they are considered as highly refined information. We here propose a novel algorithm that uses data structures found in modern CDCL SAT solvers to efficiently compute prime implicants starting from an existing model. The original aspects are (1) the algorithm is based on watched literals and a form of propagation of required literals, adapted to CDCL solvers (2) the algorithm works not only on clauses, but also on generalized constraints (3) for clauses and, more generally for cardinality constraints, the algorithm complexity is linear in the size of the constraints found. We implemented and evaluated the algorithm with the Sat4j library.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien DELORME Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 12:08:09 PM
Last modification on : Wednesday, June 15, 2022 - 6:06:59 PM



David Deharbe, Pascal Fontaine, Daniel Le Berre, Bertrand Mazure. Computing prime implicants. 13th International Conference on Formal Methods in Computer-Aided Design (FMCAD'13), Oct 2013, Portland, Oregon, United States. pp.46-52, ⟨10.1109/FMCAD.2013.6679390⟩. ⟨hal-03300802⟩



Record views