Prof. Wolfgang Thomas - Finite Automata and the Infinite

Professor Wolfgang Thomas, Chair of Computer Science at RWTH Aachen University, delivers the 2014 Milner Lecture entitled "Finite Automata and the Infinite".

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.

http://wcms.inf.ed.ac.uk/lfcs/events/milner-lectures/finite-automata-and-the-infinite/view

Recorded on Friday 3 October in the University of Edinburgh's Informatics Forum.