Modulcode:	MS0102
Englische Bezeichnung:	Automata, Logics, and Games
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	jedes Jahr (WS07/08 WS08/09 SS10 WS11/12 WS13/14 SS15 SS17 SS19)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	240 Std.
Dauer:	ein Semester
Modulkategorien:	WI (BSc Inf (15)) TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) TG (TA) (MSc Inf (2-Fach)) IG (MSc Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-LogInf Inf-Math-A Inf-Math-B Inf-Math-C Inf-TGI

Kurzfassung:

In dem Modul wird die tiefliegende Theorie erarbeitet, die endliche Automaten, die monadische Logik zweiter Stufe sowie unendliche Spiele miteinander verbindet. Ein zentraler Punkt ist der Beweis des Satzes von Rabin.

Lernziele:

Die Studierenden

• erläutern die oben genannte Theorie,
• wenden die Techniken an, die zum Aufbau der oben genannten Theorie notwendig sind,
• erarbeiten sich Primärquellen zum Thema.

Lehrinhalte:

• endliche Automaten auf unendlichen Wörtern und Bäumen
• Determinisierung von omega-Automaten
• Komplementierung von Rabin-Baumautomaten
• monadische Logik zweiter Stufe
• Paritätsspiele

Weitere Voraussetzungen:

Prüfungsleistung:

Bei wenigen Teilnehmer*innen: Anfertigung eines Portfolios. Dieses enthält die Bearbeitung von Aufgaben, die Wiedergabe von selbstständig erarbeiteten Teilen wissenschaftlicher Texte und die Dokumentation einer eigenen Kurzpräsentation. Weitere Elemente können hinzugefügt werden.

Ansonsten: schriftlich-mündliche Prüfung. An die Bearbeitung einer oder zweier schriftlicher Aufgaben schließt sich ein mündliches Prüfungsgespräch an.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

• Erich Grädel, Wolfgang Thomas, Thomas Wilke, Automata, Logic, and Infinite Games, Hrg., LNCS 2500, Berlin/Heidlberg: Springer, 2003.
• Thomas Wilke, ω-Automata, arXiv:1609.03062, 2016.
• MikoÅ‚aj Bojańczyk and Wojciech CzerwiÅ„ski, An Automata Toolbox, 2018.

Verweise:

Kommentar: