# Automata, Logic and Games:  2017-2018

 Lecturer Degrees Term Michaelmas Term 2017  (24 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.