Finite Automata and the Infinite: 2014 annual Milner Lecture

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 an informal reception.

Finite Automata and the Infinite - a Technical Survey

There will also be a short course entitled "Finite Automata and the Infinite - a Technical Survey" on Friday 3rd October. This is free and open to all, but registration is required at https://www.eventbrite.co.uk/e/milner-lecture-short-course-tickets-12632942471

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).

Further information

Milner Lectures: https://wcms.inf.ed.ac.uk/lfcs/events/milner-lectures