News & Events at Vienna
Guests and invited talks
-
Erich Grädel (Univ. Aachen): Finite and Infinite Games
[December 16, 2002] 5:00pm, Zemanek theatre, Favoritenstraße 11/ground floor/red area
Abstract. Infinite two-player games, a classical theme in mathematical logic, appear nowadays in manay areas of computer science. They model in a natural way the non-terminating interaction of a reactive system with its environment: the specification of a reactive system can be seen as a winning condition in a game, and a reactive program that fulfills the specification implements a winning strategy. Infinite games also arise as model-checking games for fixed-point logics. The central algorithmic questions are the computation of winning regions and the construction of winning strategies. These problems are solvable in linear time for finite games. However, for many important classes of infinite games (most notably for parity games) it is currently open whether winning strategies can be constructed efficiently.
[December 16, 2002] 5:00pm, Zemanek theatre, Favoritenstraße 11/ground floor/red area
Abstract. Infinite two-player games, a classical theme in mathematical
- Erich Grädel: Tutorial - Model Checking via Parity Games
[December 13th, 2002] 10:30-12:00, 13:30-15:00, [December 14th, 2002] 10:30-12:00
Seminarraum 184/2, Favoritenstraße 9/third floor
Contents:
- model-checking games
- algorithms for finite games
- parity games and fixed point logics
- determinacy via positional strategies
- algorithms for parity games
- complexity of model checking problems
