Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Course INF-59-52-K-6

Game-Theoretic Techniques in Logic and Verification (3V+1U, 6.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 6.0 CP 124 h
3 V Lecture 42 h
1 U Exercise class (in small groups) 14 h
(3V+1U) 6.0 CP 56 h 124 h

Basedata

SWS 3V+1U
CP, Effort 6.0 CP = 180 h
Position of the semester 1 Sem. in WiSe
Level [6] Master (General)
Language [EN] English
Lecturers
Area of study [INF-ALG] Algorithmics and Deduction
Livecycle-State [NORM] Active

Possible Study achievement

  • Verification of study performance: proof of successful participation in the exercise classes (ungraded)
  • Examination number (Study achievement): 65952 ("Game-Theoretic Techniques in Logic and Verification")
  • Details of the examination (type, duration, criteria) will be announced at the beginning of the course.

Contents

  • Ehrenfeucht–Fraïssé games (back and forth techniques), e.g., for first-order logic and modal logic.
  • Machine models with alternation
  • Multi-agent systems: Nash Equilibrium, CORE
  • Games with Probability: Markov Decision Processes, Stochastic games, randomized strategies.
  • Algorithms and complexity for various game problems: parity games, energy games, etc.
  • Applications to analysis of distributed protocols

Literature

  • Erich Grädel, Wolfgang Thomas, and Thomas Wilke (Eds.). "Automata logics, and infinite games: a guide to current research" Springer-Verlag, 2002.
  • Christel Baier and Joost-Pieter Katoen. "Principles of Model Checking" MIT Press, 2008.
  • Jerzy Filar and Koos Vrieze. "Competitive Markov Decision Processes" Springer-Verlag, 1997.
  • Yoav Shoham and Kevin Leyton-Brown. "Multiagent Systems - Algorithmic, Game-Theoretic, and Logical Foundations" Cambridge University Press, 2008.
  • Wojciech Jamroga. "Logical Methods for Specification and Verification of Multi-Agent Systems" Monograph Series no 10, ICS PAS, 2015.
  • Leonid Libkin. "Elements of Finite model theory" Springer, 2004.
  • Dexter Kozen. "Theory of Computation" Springer 2006.

References to Course [INF-59-52-K-6]

Module Name Context
[INF-59-52-M-6] Game-Theoretic Techniques in Logic and Verification P: Obligatory 3V+1U, 6.0 LP