Organisation

The talks are given at the end of the semester in a block.

Deadlines

25.04.	Gliederung
30.05.	Ausarbeitung
20.06.	Endgültige Fassung
01.07.	Folien
Juli	Vorträge

Schedule

Dienstag, 19. Juli
9:00	–	9:45	Felix Canavoi	Small Progress Measures
9:50	–	10:35	Sarah Winter	Discrete Strategy Improvement
11:00	–	11:45	Kevin Schewior	Lower Bounds for Strategy Improvement

Topics

Thema	Vortragende(r)	Betreuer(in)	Literatur
Discrete Strategy Improvement	Sarah Winter	Bernd Puchala	[JV00]
Small Progress Measures	Felix Canavoi	Faried Abu Zaid	[J00]
Lower Bounds for Strategy Improvement	Kevin Schewior	Roman Rabinovich	[F09]

Literature

[F09]	O. Friedmann. A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it. CoRR, vol. abs/0901.2731, 2009.
[J00]	M. Jurdzinski. Small Progress Measures for Solving Parity Games. In STACS, pp. 290-301, 2000.
[JV00]	J. Vöge and M. Jurdzinski. A Discrete Strategy Improvement Algorithm for Solving Parity Games. In CAV, pp. 202-215, 2000.

Classification

• Informatik (B.Sc.)/Seminar Informatik
• Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
• Informatik (M.Sc.)/Seminar Theoretische Informatik
• Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
• Informatik (D)/Hauptstudium/Theoretische Informatik
• Mathematik (D)/Hauptstudium/Reine Mathematik
• Informatik (S II)
• Mathematik (S II)/Hauptstudium/Modul Algebra
• Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Prerequisites

• Module Mathematical Logic
• for B.Sc. Computer Science: Module "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Contact

Erich Grädel, Faried Abu Zaid, Bernd Puchala, Roman Rabinovich