Seminar Automaten über unendlichen Wörtern (AutoInf)5 ECTS
(englische Bezeichnung: Seminar Automata on Infinite Words)
(Prüfungsordnungsmodul: Automaten über unendlichen Wörtern)

Lehrveranstaltungen:

• • Seminar Automaten über unendlichen Wörtern
    (Seminar, 2 SWS, Lutz Schröder, Mo, 14:15 - 15:45, 00.131-128; Raumreservierung bleibt bestehen. Veranstaltung wird voraussichtlich in Präsenz angeboten, bei Bedarf mit digitalen Zusatzangebot, etwa Liveübertragung via Zoom)

Inhalt:

• Büchi-, Street- und Muller-Automaten

• Unendliche Spiele und Determiniertheit

• Determinisierung, Safra/Piterman-Konstruktion

• Komplementierung

• Alternierung

• Baumautomaten

• Modaler mu-Kalkül

• Monadic Second Order Logic

Lernziele und Kompetenzen:

Fachkompetenz

Wissen

Die Studierenden geben grundlegende Definitionen und Resultate der Theorie der unendlichen Spiele und Automaten über unendlichen Strukturen wieder.

Verstehen

Die Studierenden erläutern grundlegende algorithmische Verfahren für Automaten und Spiele.

Anwenden

Die Studierenden teilen Automaten- und Spielbegriffe hinsichtlich ihrer Komplexität und ihrer Ausdrucksstärke ein.

Erschaffen

Die Studierenden bereiten Resultate des Gebiets und ihre Herleitung eigenständig zur Präsentation auf.

Lern- bzw. Methodenkompetenz

Die Studierenden erarbeiten sich selbständig den Inhalt wissenschaftlicher Veröffentlichungen und geben diesen in einem strukturierten Vortrag verständlich wieder.

Sozialkompetenz

Die Studierenden arbeiten in einer größeren Gruppe an komplexen Problemen und erläutern eigene Einsichten den Mitstudierenden in verständlicher Form.

Literatur:

Erich Grädel, Wolfgang Thomas, Thomas Wilke: Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science 2500, Springer, 2002.
Nir Piterman: From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata. Logical Methods in Computer Science 3(3) (2007)
Oliver Friedmann, Martin Lange: The Modal mu-Calculus Caught Off Guard. TABLEAUX 2011: 149-163
Damian Niwinski, Igor Walukiewicz: Games for the mu-Calculus. Theor. Comput. Sci. 163: 99-116 (1996)

Weitere Informationen:

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Informatik (Bachelor of Arts (2 Fächer))
   (Po-Vers. 2013 | TechFak | Informatik (Bachelor of Arts (2 Fächer)) | Hauptseminar | Automaten über unendlichen Wörtern)

Studien-/Prüfungsleistungen:

Automaten über unendlichen Wörtern (Prüfungsnummer: 31261)

Prüfungsleistung, Seminarleistung, benotet, 5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

weitere Erläuterungen:
Die Prüfungsleistung besteht in einer Ausarbeitung und einem 90-minütigen erfolgreichen Vortrag.

Prüfungssprache: Deutsch oder Englisch

Erstablegung: WS 2020/2021, 1. Wdh.: SS 2021

1. Prüfer:

Lutz Schröder