Skip to main content

Automata, Logic and Games:  2017-2018

Lecturer

Degrees

Schedule C1 (CS&P)Computer Science and Philosophy

Schedule C1Computer Science

Schedule C1Mathematics and Computer Science

Schedule CMSc in Computer Science

MSc in Mathematics and Foundations of Computer Science

Term

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.