Logic, Automata, Games, and Algorithms
Speaker:
Moshe Vardi, Rice University
Date and Time:
Wednesday, July 13, 2011 - 4:00pm to 5:00pm
Location:
Fields Institute, Room 230
Abstract:
The automata-theoretic approach to decision procedures, introduced by Buechi, Elgot, Rabin and Trakhtenbrot in the 1950s and 1960s, 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 overview talk we describe the path from logic to algorithms via automata and games.