Modulcode:	infALG-01a
Englische Bezeichnung:	Automata, Logic, and Games
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	unregelmäßig (SS23)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21))
Lehrsprache:	Englisch
Voraussetzungen:	infBL-01a infAAK-01a

Kurzfassung:

This course covers automata on infinite words, automata on infinite trees, and games on graphs, and their connection with logic. It culminates in a proof of Rabin's theorem, which states that the monadic second-order theory of two successors is decidable. - Various applications in computer science are discussed.

Lernziele:

Students

• apply automata theory in logic settings,
• adapt and extend automata theory (see above) an the theory of graph games as needed,
• use the intimate connections between automata theory and games on graphs,
• explain issues regarding expressiveness, complexity, and decidability for monad second-order logic on words and the infinite binary tree.

Lehrinhalte:

• finite-state automata on infinite words and infinite trees
• monadic second-order logic over infinite words and the infinite binary tree
• games on graphs, determinacy
• complexity of solving parity games (and the logical theories discussed)

Weitere Voraussetzungen:

Prüfungsleistung:

Depending on the number of students:

• portfolio (in combination with a short presentation as a prerequisite)
• oral exam (with a preceding working phase)
• written exam.

Lehr- und Lernmethoden:

• lecture: presentations by lecturer and discussions/work in small groups
• classroom exercise: discussion of solutions of/approaches to home problems

Verwendbarkeit:

Literatur:

J.-É Pin. 2021. Handbook of Automata Theory. EMS Press, Berlin.

Verweise:

Kommentar:

Alternative prerequisite: Inf-TGI and Inf-LogInf.