4 credits

In the course, you will learn how specify and verify properties that give formal meaning to words such as 'eventually' and 'until' and how to automatically verify that systems satisfy such properties. You will learn about more general types of finite state machines: machines run continuously, such as a web server, and machines that accept not only words (strings) but also trees (tree automata). You will learn about some of the widely used results such as decision procedures for linear integer arithmetic, and some classic deep results such as the decision procedure for monadic second-order logic over (possibly infinite) trees. You will also see how these results can be applied to verification, but also synthesis of systems that are correct by construction.

Objectives: Many major hardware (Intel, IBM) and software (Microsoft) companies are now using the technique of Model Checking in practice. Examples of its use include the verification of VLSI circuits, communication protocols, software device drivers, real-time embedded systems, and security algorithms. The works of A. Pnueli, E. Clarke, E.A Emerson and J. Sifakis on algorithmic verification of systems using the Model Checking has been awarded the 1996 and 2007 Turing awards. The basis of this work is the relation of logic with automata theory, which was introduced by the seminal works of Buechi (1960) and Rabin (1969). This course is intended to introduce the student to these techniques, focusing on decision methods for classical non-interpreted logics and integer arithmetic theories.

Schedule: (lectures and exercises): Fridays 13:15-16:00

First lecture: 18.9.2009
Last lecture: 18.12.2009

Location: BC 355

Instructors:

• Radu Iosif
• Barbara Jobstmann

Organized by: Viktor Kuncak