Computability in Europe 2006
Logical Approaches to Computational Barriers

Logic, Automata, Games, and Algorithms

Speaker: Moshe Y. Vardi


The automata-theoretic approach to decision procedures, introduced by Buechi, Elgot, and Trakhtenbrot in the late 1950s, is one of the most fundamental approaches to decision procedures. Recently, this approach has found industrial applications in formal verification of hardware and software systems. The path from logic to practical algorithms goes not only through automata, but also through games, whose algorithmic aspects were studies by Chandra, Kozen, and Stockmeyer in the late 1970s. In this tutorial we describe the path from logic to algorithms via games and automata.

websites: Arnold Beckmann 2008-03-09