A SAT Characterization of Boolean-Program Correctness | Zendy

K. Rustan | Zendy; Mirka Leino | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A SAT Characterization of Boolean-Program Correctness

Author(s) -

K. Rustan,

Mirka Leino

Publication year - 2003

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-40117-2

DOI - 10.1007/3-540-44829-2_7

Subject(s) - binary decision diagram , correctness , computer science , boolean satisfiability problem , model checking , boolean function , boolean expression , programming language , theoretical computer science , program analysis , true quantified boolean formula , boolean data type , algorithm

Boolean programs, imperative programs where all variables have type boolean, have been used effectively as abstractions of device drivers (in Ball and Rajamani's SLAM project). To find errors in these boolean programs, SLAM uses a model checker based on binary decision diagrams (BDDs). As an alternative checking method, this paper defines the semantics of procedure-less boolean programs by weakest solutions of recursive weakest-precondition equations. These equations are then translated into a satisfiability (SAT) problem. The method uses both BDDs and SAT solving, and it allows an on-the-fly trade-off between symbolic and explicit-state representation of the program's initial state.

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