Course

Infinite Games

Lecturer:	Martin Zimmermann
Assistant:	Felix Klein
Lectures:	Thursdays, 10:15-12:00, E1.3 HS 003
Tutorials:	Tuesdays 16:00-18:00, E2 5 SR U.11

News

We uploaded the final version of the lecture notes with all known errors fixed. There are no major changes against previous versions.
The slides of the last lecture are available for download. slides, handout
There was an error in the 13th exercise sheet. A corrected version is now online.
The 13th exercise sheet will be the last sheet for this
semester. Your overall score has to be strictly greater than 92
points to get admitted to the exam and it has to be strictly greater
than 175 points to get a bonus.
The course evaluation will take place on the 9. January 2014 in the lecture.
There was an error in the fifth exercise sheet. A corrected version is now online.
Please register for the exam in HisPos (Deadline: 17.11.2013)
There was a small error in the third exercise sheet. A corrected version is now online.
There will be no tutorial on the 29. Oct. 2014.
The first part of the lecture notes and the first exercise sheet are available under Exercises.
The overview slides presented in the first lecture are available for download.

Topics

Introduction: reachability and safety games, Büchi and co-Büchi games, parity games.
Memory: finite-state strategies, reductions, Muller games, limits of reductions.
Games on infinite graphs: pushdown games, pushdown strategies.
Application: tree automata, MSO over trees, Rabin’s theorem.

Textbooks

Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.)
Automata, Logics, and Infinite Games: A Guide to Current Research
Springer, Berlin;
Lecture Notes in Computer Science 2500
2nd Print (1. November 2005)
ISBN-10: 0387292373

Advanced Lecture (6 CP)
Winter Term 2013/2014