# Milner Lectures

Before he left Edinburgh for Cambridge, Robin Milner very kindly donated a sum of money to fund an annual lecture in Computer Science at the University of Edinburgh, to be given...

... by someone from outside the University who has done or is doing excellent and original theoretical work which has a perceived significance for practical computing. The spirit of the proposal is to keep a live connection between theory and application in computer science.

The Milner Lecture is a public lecture which is held annually and open to all. The speaker visits for several days and usually gives one or more other technical talks.

Robin Milner was one of the founding members and the first director of the Laboratory for Foundations of Computer Science. He then moved to Cambridge where he held a Research Professorship in the __Computer Laboratory__. He passed away on 20 March 2010, obituaries can be found at the Guardian and the University of Cambridge.

**Milner Lecture 2014**

**Finite Automata and the Infinite**

**Professor Wolfgang Thomas**

**RWTH Aachen University, Germany**

** **

*4:00 pm, Thursday 2 October *

*4:00 pm, Thursday 2 October*

*G.07 Informatics Forum, University of Edinburgh*

*G.07 Informatics Forum, University of Edinburgh*

**Abstract:**

Finite automata are a simple model of computation, yet they offer intriguing difficulties – and results – when used in the description and analysis of infinite objects. These objects may arise as infinite-state systems, infinite computations (such as computation trees), or a combination of both. Automata serve here as a tool to make logic over infinite structures effective, which in turn has led to many applications in algorithmic verification and synthesis. The lecture offers a personal account of the development of automata theory with this focus. Starting from a historical discussion, we give an intuitive explanation of central results (regarding automata over infinite strings and trees, and infinite games), and then address some open problems on the interplay between automata theory and logic.

The lecture will be followed by a informal reception.

**Biography:**

Wolfgang Thomas obtained the degree of M.Sc. (1972) from the University of Bristol and the doctoral degree (1975) from the University of Freiburg, Germany, both in mathematical logic. He was professor for computer science at RWTH Aachen University 1982-1989, at the University of Kiel 1989-1998, and since 1998 again in Aachen on the chair “Logic and Theory of Discrete Systems”. He co-authored a monograph on mathematical logic and is known for numerous contributions to automata theory and logic, among them influential survey papers. He served in many PCs (chairing, e.g., FoSSaCS, STACS, ICALP) and as editor of journals, among them ACM Transactions of Computational Logic and Logical Methods in Computer Science. He is doctor honoris causa of the Ecole Nomale Supérieure de Cachan and the University of Mons, member of Academia Europaea, and Fellow of EATCS (European Association of Computer Science).

**Short Course: Finite Automata and the
Infinite - a Technical Survey**

**Professor Wolfgang Thomas**

**RWTH Aachen University, Germany**

** **

*9.00am-5:00 pm, Friday 3 October *

*9.00am-5:00 pm, Friday 3 October*

*4.31/4.33 Informatics Forum, University of Edinburgh*

*4.31/4.33 Informatics Forum, University of Edinburgh*

### We are fortunate that Prof Thomas will also be giving a short course the following day, going into the topic of the Milner Lecture in more depth. This course is free and open to all but registration is required.

**Abstract: **

Finite automata over infinite strings and trees have opened a new chapter of effective model theory, mostly in connection with monadic second-order logic (MSO-logic). The classical results of the 1960’s, by Büchi, McNaughton, Rabin, and others have been a subject of intensive study over several decades, giving (1) refined and streamlined presentations, (2) extensions especially on MSO-logic over infinite transition systems, and (3) an adaption of the fundamental results towards practical use.

We survey the state of the art with a focus on the first two aspects, proceeding in four stages:

• Büchi automata and their determinization

• Regular infinite games

• Rabin’s tree theorem

• Muchnik’s theorem, unfolding, and the pushdown hierarchy

The Milner lecture (“Finite Automata and the Infinite”) may be considered as a motivating introduction to this course.

### Register for the short course **here**

### Lunch will be provided so please note any dietary requirements when registering

### Past Lectures

## Nominations for future lecturers