« November 2019 »
November
MoTuWeThFrSaSu
123
45678910
11121314151617
18192021222324
252627282930
Uni-Logo
You are here: Home Teaching Winter Term 2019/20 Decision Procedures (Lecture)
Document Actions

Decision Procedures

Decision Procedures are the basis for program verification: The task of program verification is to give a formal proof that a program meets its specification. This amounts to determining the truth value of a logical formula. A decision procedure is an algorithm that can for a certain type of formulas decide whether the formula is true or false. We will investigate decision procedures for different logics. Starting with propositional logic we will investigate decision procedures for logics with integers, reals, recursive structures (lists and trees), arrays, etc.

Course type Lecture
Instructors Andreas Podelski, Jochen Hoenicke, Tanja Schindler
Lecture Tuesday, 14:00–16:00, Bld. 106, Room 00-007
Thursday, 14:00–15:00, Bld. 106, Room 00-007
Exercise Thursday, 15:00–16:00, Bld. 106, Room 00-007
First session Tuesday 22.10.2019
Language of instruction English
Credits 6
Exams t.b.a.
Course Catalog Decision Procedures - Lecture
Decision Procedures - Exercises

 

News

    • Sep. 30: Homepage online.

     

    Formalia

    Admission criteria

    Half of the maximum points from the exercises have to be achieved in order to be admitted for the exam. There will be an exercise sheet each week, usually with three exercises and a maximum of 12 points. You can usually hand in your submission before the lecture on Tuesday -- alone or in groups of two.

    Exam

    The exam will be oral or written, depending on the number of participants.

    Please register via the examination office as usual.

     

    Resources

    Course Materials

    Textbooks

    • Bradley A. R., Manna Z.: The Calculus of Computation: Decision Procedures with Applications to Verification, 2007, Springer, New York.
    • Kroening D., Strichmann O.: Decision Procedures - An Algorithmic Point of View, 2008, Springer.

    Papers

    • B. Dutertre, L. de Moura: Integrating Simplex with DPLL(T), Technical Report, SRI_CSL-06-01, 2006.
    • B. Dutertre, L. de Moura: A fast linear-arithmetic solver for DPLL(T), CAV 2006.

    Tools and Standards

    • SMTInterpol  (Interpolating SMT solver developed by us --- the chair of software engineering)
    • CVC4 (SMT solver developed by Stanford University and the University of Iowa)
    • Yices (SMT solver developed by Stanford Research Institute)
    • Z3 (SMT solver developed by Microsoft Research)
    • SMTLIB (A standard for encoding SMT problems which is read by many solvers)
    • PiVC (Tool for program verification by Stanford University)

    Old Decision Procedures Lectures

     

    Personal tools