[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
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.

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 Forschungsaufenthalten 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"

-- 
Schwarz Therese
Vienna University of Technology - Database & AI Group
A-1040 Vienna, Favoritenstr. 9-11/Stg.2/3. Stock/1842
Tel.: ++43(1)58801-18404, Fax: ++43(1)58801-18492
http://www.dbai.tuwien.ac.at/staff