August - November 2026
Instructor: B. Srivathsan
The objective of the course is to discuss some of the developments in automata theory over the last twenty years. This is by no means an exhaustive list.
The course will be divided into four modules.
| #Lecture | Date | Topic | Slides / Notes | Problem Sheet |
|---|---|---|---|---|
| Module 1: History-determinism | ||||
| 1 | 03 Aug 2026 | Introduction to History-determinism through examples | Slides | Assignment 1 |
| 2 | 05 Aug 2026 | History-determinism coincides with good-for-gameness in omega-automata | Slides | Assignment 2 |
| 3 | 07 Aug 2026 | Introduction to token games and Joker games | Slides | |
| 4 | 11 Aug 2026 | From 2-tokens to k-tokens, and then to Joker | Slides | |
| 5 | 13 Aug 2026 | 2-token games to simulation-equivalent subautomaton | Slides | |
| 5 | 13 Aug 2026 | Simulation games, guidability, winning token games from everywhere | Slides | |
| 6 | 19 Aug 2026 | Even wins 2-token game implies there is a simulation-equivalent subautomaton where Eve wins from everywhere | Slides | |
| 6 | 21 Aug 2026 | Eve wins Joker game implies there is a simulation-equivalent subautomaton where Eve wins 1-token game from everywhere | Theorem 3.34 of [1] | |
| 7 | 28 Aug 2026 | Characterizing HD-ness in coBüchi Automata - Part I | Slides | |
| 8 | 31 Aug 2026 | Characterizing HD-ness in coBüchi Automata - Part II | Slides | |
| 9 | 02 Sep 2026 | Characterizing HD-ness in coBüchi Automata - Part III | Slides | |
| 10 | 07 Sep 2026 | Characterizing HD-ness in coBüchi Automata - Part IV | Slides | |
| 11 | 07 Sep 2026 | Characterizing HD-ness in Büchi Automata - Part I | Slides | |
| 12 | 09 Sep 2026 | Characterizing HD-ness in Büchi Automata - Part II | Slides | |
| 13 | 16 Sep 2026 | Characterizing HD-ness in Büchi Automata - Part III | Slides | |
| 14 | 18 Sep 2026 | Summary of the module | Slides | |