Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Logic, Automata, Games, and Algorithms

Edit abstract data

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 Valid HTML 4.01! Valid CSS!