Advanced Lecture (Vertiefungsvorlesung), Summer Term 2016, 6 CP
|People:||Martin Zimmermann, Alexander Weinert|
|Lecture Room:||E1 3, HS 003|
|Tutorials:||Mondays, 14:00-16:00, E1 3, Room 016|
|Exams:||End of Term: Mon, Aug 1st, 2016, 10 am|
|End of Semester: Tue, Sep 20th, 2016, 10 am|
|Exam room:||E1 3, HS 003|
This course is aimed at mathematically interested students that enjoy beautiful proofs that capture intuitive descriptions of strategies, appreciate deep connections to logics, and value an occasional hard open problem. Also, you should like to play games: we plan to have a tournament where students will submit games to a pool that can be be solved in order to earn points towards exam admission. Besides this, we will have regular problem sets as well.
Many of todays problems in computer science are no longer concerned with programs that transform data and then terminate, but with non-terminating systems which have to interact with a possibly antagonistic environment. The emergence of so-called “reactive systems” requires new approaches to verification and synthesis. Over the course of the last fifty years it turned out to be very fruitful to model and analyze reactive systems in a game-theoretic framework, which captures the antagonistic and strategic nature of the interaction between the system and its environment.
In this lecture, we will study different types of two-player games of infinite duration: typical questions we will answer are “how hard is it to determine the winner of a given game?”, “what kind of strategy does the winner need to win the game?”, and “does every game have a winner?”. Also, we discuss applications of infinite games in logics by proving Rabin’s theorem, sometimes called the “mother of all decidability results”.
- Introduction: reachability and safety games, Büchi and co-Büchi games, parity games.
- Memory: finite-state strategies, reductions, Muller games, limits of reductions, and non-determined games.
- Application: tree automata, MSO over trees, Rabin’s theorem.
- We will follow the lecture notes from the winter term 2013-14, which will be updated during the term: lecture-notes.pdf