Advance Logics (2021)
This course invites you to discover the close links existing between certain logical formalisms, automata and game theory. Discussed topics include, on the side of logics, second-order monadic logic, Presburger arithmetic and linear time logic. We will see how these can be compiled to automata, such as finite automata, Büchi automata and tree automata, yielding effective decision procedures. We will also touch topics of game theory, notably parity games, to reason about alternating automata.
News
- Jan 26: The web-page will be filled continuously with course material over the semester.
Schedule
| Date | Contents | Material |
| W1 | finite automata | (slides, exercises) |
| W2 | weak monadic second-order logic (WMSO) | (slides, exercises) |
| W3 | Presburger arithmetic, MONA | ( slides, presburger.mona, nader.mona, hyman.mona ) |
| W4 | Alternating finite automata | (slides, exercises, NFA.hs) |
| W5 | Alternating finite automata and games | (slides) |
| W6 | Tree automata | (slides, exercises) |
| W7 | Büchi automata | (slides, exercises) |
| W8 | Linear time logic | (slides) |
Grading
- 1/4 mini projects
- 1/4 exercises
- 1/2 final exam
Contact
Martin Avanzini (
(martinyavanzinixinriayfr)[x ↦ @, y ↦ .]
)