A Verified SAT Solver Framework with Learn, Forget, Restart, and Incrementality (Extended Abstract)

Jasmin Christian Blanchette 1, 2, 3 Mathias Fleury 2, 3 Christoph Weidenbach 2
1 Inria Nancy - Grand Est
2 MPII - Max-Planck-Institut für Informatik
3 VERIDIS - Modeling and Verification of Distributed Algorithms and Systems
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We developed a formal framework for CDCL (conflict-driven clause learning) in Isabelle/HOL. Through a chain of refinements, an abstract CDCL calculus is connected to a SAT solver expressed in a functional programming language, with total correctness guarantees. The framework offers a convenient way to prove metatheorems and experiment with variants. Compared with earlier SAT solver verifications, the main novelties are the inclusion of rules for forget, restart, and incremental solving and the application of refinement.
Type de document :
Communication dans un congrès
Isabellle Workshop 2016, Aug 2016, Nancy, France
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01401807
Contributeur : Jasmin Christian Blanchette <>
Soumis le : mercredi 23 novembre 2016 - 17:44:39
Dernière modification le : jeudi 11 janvier 2018 - 06:23:13
Document(s) archivé(s) le : mardi 21 mars 2017 - 00:46:56

Fichier

sat_abs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01401807, version 1

Collections

INRIA | LORIA | LORIA-FM | UNIV-LORRAINE

Citation

Jasmin Christian Blanchette, Mathias Fleury, Christoph Weidenbach. A Verified SAT Solver Framework with Learn, Forget, Restart, and Incrementality (Extended Abstract). Isabellle Workshop 2016, Aug 2016, Nancy, France. 〈hal-01401807〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

28

Contact


archive-ouverte@inria.fr