The Mechanical Verification of a DPLL-Based Satisfiability Solver | Zendy

Natarajan Shankar | Zendy; Marc Vaucher | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Mechanical Verification of a DPLL-Based Satisfiability Solver

Author(s) -

Natarajan Shankar,

Marc Vaucher

Publication year - 2011

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2011.03.002

Subject(s) - dpll algorithm , computer science , satisfiability , boolean satisfiability problem , satisfiability modulo theories , solver , theoretical computer science , predicate abstraction , inference , algorithm , formal verification , programming language , model checking , artificial intelligence , jitter , telecommunications , phase locked loop

Recent years have witnessed dramatic improvements in the capabilities of propositional satisfiability procedures or SAT solvers. The speedups are the result of numerous optimizations including conflict-directed backjumping. We use the Prototype Verification System (PVS) to verify a satisfiability procedure based on the Davis–Putnam–Logemann–Loveland (DPLL) scheme that features these optimizations. This exercise is a step toward the verification of an efficient implementation of the satisfiability procedure. Our verification of a SAT solver is part of a larger program of research to provide a secure foundation for inference using a verified reference kernel that contains a verified SAT solver. Our verification exploits predicate subtypes and dependent types in PVS to capture the specification and the key invariants

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research