Automata, Logic and Games: 2009-2010
Information
|
Lecturer |
|
|
Degrees |
Schedule C1 — Honour School of Computer Science Part C — Honour School of Mathematics and Computer Science Schedule C — MSc in Computer Science |
|
Term |
Hilary Term 2010 (16 lectures) |
Overview
To introduce the mathematical theory underpinning the Computer-Aided Verification of computing systems. The main ingredients are:
- Automata (on infnite words and trees) as a computational model of state-based systems.
- Logical systems (such as temporal and modal logics) for specifying operational behaviour.
- Two-person games as a conceptual basis for understanding interactions between a system and its environment.
Learning outcomes
At the end of the course students will be able to:
- Describe in detail what is meant by a Buchi automaton, and the languages recognised by simple examples of Buchi automata.
- Use linear-time temporal logic to describe behaviourial properties such as recurrence and periodicity, and translate LTL formulas to Buchi automata.
- Use S1S to define omega-regular languages, and give an account of the equivalence between S1S definability and Buchi recognisability.
- Explain the intuitive meaning of simple modal mu-calculus formulas, and describe the correspondence bewteen property-checking games and modal mu-calculus model checking.
Prerequisites
Knowledge of first-order predicate calculus will be assumed. Familiarity with the basics of Finite Automata Theory and Computability (for example, as covered by the course, Models of Computation) and Complexity Theory would be very helpful. Candidates who do not have the required background are expected to have taken the course, Introduction to the Foundations of Computer Science.
Synopsis
- Automata on infinite words. Buchi automata: Closure properties. Determinization and Rabin automata.
- Nonemptiness and Nonuniversality problems for Buchi automata.
- Linear temporal logic and alternating Buchi automata.
- Modal mu-calculus: Fundamental Theorem, decidability and finite model property. Parity Games and the Model-Checking Problem: memoryless determinacy, algorithmic issues.
- Monadic Second-order Logic and its relationship with the modal mu-calculus.
Reading list
Selected parts from:- J. Bradfield and C. P. Stirling. Modal logics and mu-calculi. In J. Bergstra, A. Ponse, and S. Smolka, editors, Handbook of Process Algebra, pages 293{332. Elsevier, North-Holland, 2001.
- B. Khoussainov and A. Nerode. Automata Theory and its Applications. Progress in Computer Science and Applied Logic, Volume 21. Birkhauser, 2001.
- C. P. Stirling. Modal and Temporal Properties of Processes. Texts in Computer Science. Springer-Verlag, 2001.
- W. Thomas. Languages, Automata and Logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3. Springer-Verlag, 1997.
- M. Y. Vardi. An automata-theoretic approach to linear temporal logic. In Logics for Concurrency: Structure versus Automata, ed. F. Moller and G. Birtwistle, LNCS vol. 1043, pp. 238-266, Springer-Verlag, 1996.
The only copy of the Vardi book is in the RSL on open shelves. However, the article in question is availabe in .pdf form online at this address:
http://folli.loria.fr/cds/1998/pdf/degiacomo-nardi/vardi.pdf