[Acpc-l] INFORMATIKKOLLOQUIUM: 16.12.2002 17h00 E. Grädel : Endliche und unendliche Spiele

[Therese Schwarz]

Der Fachbereich Informatik und die Österreichische Computer Gesellschaft
laden zu folgendem Vortrag ein:
======================================================

Endliche und unendliche Spiele

Prof. Erich Grädel
Math. Foundations of Computer Science
Aachen University of Technology
graedel@informatik.rwth-aachen.de
www-mgi.informatik.rwth-aachen.de


Datum: 16.12.2002, 17.00 Uhr
Ort: Zemanek Hörsaal, Favoritenstraße 11/Erdgeschoß/roter Bereich

Abstract: Unendliche Zwei-Personen-Spiele, ein klassisches Thema der
mathematischen Logik, treten heute in vielen Anwendungen auf. Sie
modellieren auf natürliche Weise die nicht-terminierende Interaktion reaktiver
Systeme mit ihrer Umgebung: die Spezifikation eines reaktiven Systems
entspricht einer Gewinnbedingung in einem solchen Spiel, ein reaktives
Programm, welches der Spezifikation genügt, implementiert eine
Gewinnstrategie. Unendliche Spiele treten auch als Model-Checking-Spiele
von Fixpunktlogiken auf.
Die zentralen algorithmischen Probleme sind die Berechnung von Gewinn-
mengen und die Konstruktion von Gewinnstrategien. Während man diese
Probleme für endliche Spiele in linearer Zeit lösen kann, ist es für wichtige
Klassen unendlicher Spiele (insbesondere für Paritätspiele) noch offen, ob
Gewinnstrategien effizient konstruierbar sind.

Abstract in English:
Finite and Infinite Games

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.


Short Biography: Erich Grädel ist Professor für Mathematische Grundlagen
der Informatik an der RWTH Aachen. Er hat in Basel (Schweiz) Mathematik,
Physik und Geschichte studiert und dort 1987 promoviert. Nach Forschungs-
aufenthalten in Pisa und Berkeley und Lehraufträgen an der Universität Zürich
und der ETH Zürich hat er 1991 an der Universität Basel habilitiert. Seit 1993
ist er Professor in Aachen. Er hatte seither Gastprofessuren in Wien, Paris 
und
Bordeaux.

Seine wichtigstes Arbeitgebiet ist die Mathematische Logik und ihre
Anwendungen in der Informatik, insbesondere - algorithmische Probleme der
Logik und der Zusammenhang von Logik und Komplexität, - die Theorie
unendlicher Spiele, - die endliche und algorithmische Modelltheorie, -
Anwendungen von Logik, Automaten und Spielen für die Synthese und
Validierung diskreter Systeme.

Prof. Erich Grädel ist Koordinator des europäischen Research Training
Network Games and Automata for Synthesis and Validation (GAMES).

Weitere Informationen über Erich Grädel und die von ihm geleitete
Forschungsgruppe finden sich auf www-mgi.informatik.rwth-aachen.de


--------------------------------------------------------------------------------------------
"Der Fachbereich Informatik wird unterstützt von Siemens AG Österreich"