Arbeitsgemeinschaft Logik und Automaten

Vorträge im Wintersemester 2011/2012

Regret-Minimierung als Lösungskonzept für unendliche Spiele

Freitag, 2. Dezember 2011, 11:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Daniel Franzen
RWTH Aachen University
Imperfect Recall and Counter Parity Games

Dienstag, 6. Dezember 2011, 14:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Łukasz Kaiser
LIAFA, Paris

Zusammenfassung:

We study a class of omega-regular games with imperfect information and imperfect recall, for which we present an automata-based solution method. Furthermore, we show a reduction from a class of counter parity games to games with this kind of imperfect recall. By combining the two results, we obtain an elementary algorithm for solving counter parity games, which leads to improved complexity bounds for model checking quantitative variants of the mu-calculus.