Computing prime implicants - Université d'Artois Access content directly
Conference Papers Year : 2013

Computing prime implicants


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.
Not file

Dates and versions

hal-03300802 , version 1 (27-07-2021)



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⟩
302 View
0 Download



Gmail Facebook Twitter LinkedIn More