Automatentheorie – Proseminar
Übersicht
- Dozent: Prof. Dr. Peter Thiemann
- Assistenz: Janek Spaderna, Leonardo Mieschendahl
- Raum: SR 00 014, Gebäude 078
- Erstes Treffen: 14.10.2025, 16:00 Uhr
| Datum | Änderungen/Neuigkeiten |
|---|---|
| 07.10. | Themen, Informationen zum Seminarsablauf |
| 10.10. | weitere Themen |
| 29.10. | Vortragstermine veröffentlicht |
Termine
| Datum | Thema | Vortrag | Betreuer |
|---|---|---|---|
| 02.12. | (2) Schwache, monadische Logik zweiter Stufe | Moritz | PT |
| (3) Alternierende, endliche Automaten | Fabian | JS | |
| 09.12. | (4) Sternfreie Sprachen | Carola | LM |
| (12) Automaten auf endlichen Bäumen | Olivia | JS | |
| 16.12. | Derivatives of regular expressions | Peter | LM |
| Partial derivatives of regular expressions … | Leon | JS | |
| 13.01.2026 | (5) Automaten auf unendlichen Bäumen | Henry | JS |
| (6) Komplementierung von Büchi-Automaten | Lukas | PT | |
| 20.01.2026 | (7) Weitere Akzeptanzbedingungen | Joa Jeremias | JS |
| (8) Determinisierung von Büchi-Automaten | Kristin | PT | |
| 27.01.2026 | (10) Alternierende Automaten | Lena | JS |
| Symbolic tree automata | Maurice | PT | |
| 03.02.2026 | (9) Entscheidungsverfahren für ω-Automaten | Joshua | PT |
Alle Sitzungen starten um 16:00 s.t.
Ablauf des Seminars
-
Teilnahme am ersten Treffen (14.10.2025), in dem wir die Themen (siehe unten) vorstellen. Themenwünsche können bereits vorher per Mail eingereicht werden (bitte an Prof. Thiemann und Janek Spaderna).
-
Seminarsplätze werden zugeteilt, Themen final vergeben, sowie Betreuer und Vortragstermine bekannt gegeben.
-
In einem ersten Treffen mit dem Betreuer werden eventuelle Fragen geklärt, relevante Literatur besprochen und ein erster, sehr grober Entwurf des Vortrags entwickelt.
(Deadline: vier Wochen vor der Präsentation) -
In einem zweiten Treffen wird dem Betreuer der inzwischen konkret ausgearbeitete Plan für den Vortrag vorgestellt und dann gemeinsam besprochen. Alle Materialien für den Vortrag (siehe unten) sollten bereits fertig sein und werden ebenfalls besprochen.
(Deadline: eine Woche vor der Präsentation) -
Anwesenheit bei den anderen Seminarsvorträgen
Die Seminarsteilnehmer:innen sind selbst dafür zuständig, passende Besprechungstermine mit dem zuständigen Betreuer zu vereinbaren.
Vortrag
-
Der Vortrag (40 Minuten) erfolgt an der Tafel und muss einen nicht trivialen Beweis präsentieren. Der Vortrag erfolgt ohne Folien und darf nicht abgelesen werden; stichpunktartige Notizen sind sinnvoll.
-
Ziel des Vortrags ist, dass die Zuhörerschaft (Informatik-Bachelorstudierende, keine Experten) die Möglichkeit hat, etwas Neues über ein interessantes Thema zu lernen. Wie gut das gelingt, wird einen Großteil der Note bestimmen.
Themen und Literatur
Grundlage des Proseminars ist das Buch „Automatentheorie und Logik“ von Hofmann und Lange. Ein Vortrag entspricht einem Kapitel im Buch vom Umfang etwa einer Vorlesungsstunde. Das Buch ist online (über das Universitätsnetzwerk, z. B. via VPN) und in der Fakultätsbibliothek verfügbar.
Außerdem stehen folgende Themen zur Verfügung, die nicht im Buch enthalten sind:
-
Brzozowski-Ableitungen
JA Brzozowski. Derivatives of regular expressions. J. ACM, 11(4):481–494, 1964.
-
Antimirov-Ableitungen
VM Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci., 155(2):291–319, 1996.
-
Symbolische Baum-Automaten
M Veanes, NS Bjørner. Symbolic tree automata. Inf. Process. Lett., 115 (3):418–424, 2015.