Seminar
Decision procedures for verification of computer systems
| Supervisor |
Dr. Calogero G. Zarba
- REACT Group, Universitaet des Saarlandes
|
| Date and time |
Tuesday, November 21, 2006
at
5:30 PM
- caffè, tè & C. ore 17.00
|
| Place |
Ca' Vignal 3 - Piramide,
Floor 0,
Hall Verde
|
|
Contact person
|
Maria Paola
Bonacina
|
| Publication date |
October 12, 2006
|
| Department |
|
Summary
Safety-critical computer systems are used more and more inside aircrafts, trains, cars, and other artifacts whose failure can endanger human life.
The rigorous mathematical analysis and verification of safety-critical computer systems ultimately relies on the availability of robust, general, and fast decision procedures for logical theories modelling simple data types (such as integer, reals, and bit-vectors), functional data structures (such as lists, arrays, sets, multisets, and graphs), and pointer-based data structures (such as linked lists and binary search trees).
In this talk we describe how decision procedures are used in the verification of safety-critical computer systems. Furthermore, we present a general algorithm that can decide the satisfiability of every quantifier-free verification condition spanning over simple data types, functional data structures, and pointer-based data structures. This algorithm is based on the eager approach to decision procedures: the verification condition to be checked for satisfiability is converted into an equisatisfiable propositional formula, which can be sent to a state-of-the-art BDD package or SAT solver.
|
