Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
lat1 [2009/09/18 12:47] vkuncak |
lat1 [2009/09/18 12:48] (current) vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Logic and Automata Theory ====== | + | ====== Doctoral Course: Logic and Automata Theory ====== |
| + | |||
| + | **4 credits** | ||
| **In the course, you will learn how specify and verify properties that | **In the course, you will learn how specify and verify properties that | ||
| Line 14: | Line 16: | ||
| ====== Introductory Lecture: Today 1pm-2pm in BC 355 ====== | ====== Introductory Lecture: Today 1pm-2pm in BC 355 ====== | ||
| - | |||
| - | A course in the [[http://phd.epfl.ch/edic|EPFL Doctoral Program in Computer and Communication Sciences]] | ||
| - | |||
| - | **4 credits** | ||
| **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. | **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. | ||
| - | |||
| - | **Syllabus**: | ||
| - | - Classical first- and second-order logic, finite word and tree automata, closure properties and language emptiness. | ||
| - | - Relationship between Weak Monadic Second-Order Logic and finite automata. Infinite automata on words (Buechi, Mueller) and on trees (Rabin) automata, and their relationship with Monadic Second-Order Logic. | ||
| - | - Game theory. Proof of Rabin's Complementation Theorem. Application of game theory to Mu-calculus, a widely used tool for specification and verification of systems. | ||
| - | - Logical theory of integer arithmetic. Decidability results using both quantifier elimination and automata theory. Cobham's base dependence theorem. | ||
| **Schedule**: (lectures and exercises): Fridays 13:15-16:00 | **Schedule**: (lectures and exercises): Fridays 13:15-16:00 | ||