Algebraische und logische Aspekte der Automatentheorie (WiSe 2023/24)
| Dozent | Prof. Dr. Stefan Milius |
| Umfang | Seminar, 2 SWS, ECTS-Credits: 5 |
| Zeit und Ort | Di, 10:15-11:45 Uhr, 01.131-128 (Cauerstr. 11) |
| Zielgruppe | Informatik BSc (ab 5. Semester), Informatik MSc, Mathematik |
| Beginn | Dienstag, 17.10.2023 |
StudOn
Als Online-Platform der Lehrveranstaltung benutzen wir StudOn. Dort werden auch sämtliche Materialien bereit gestellt.
Bitte tragen Sie sich in den StudOn-Kurs ein:
| StudOn-Kurs | Anmeldung |
Inhalt des Seminars
Automaten als mathematische Formalisierung zustandsbasierter Systeme gehören zu den wichtigsten Werkzeugen der Theoretischen Informatik und besitzen zahlreiche Anwendungen, von der Compilerentwicklung bis zur Verifikation reaktiver Systeme. In dieser Veranstaltung, die an die Anfängervorlesungen des Informatikstudiums anknüpft, werden Querverbindungen zwischen der Automatentheorie und Gebieten der Mathematik (Algebra, Topologie und Logik) hergestellt:
- Erkennung von regulären Sprachen durch Monoide und Halbgruppen
- Proendliche Gleichungen und Varietäten von Sprachen
- Logische Beschreibung regulärer Sprachen, Ehrenfeucht-Fraïssé-Spiele
- Automaten, Algebra und Logik auf unendlichen Wörtern und Bäumen
Slogan (Marshall Stone): “Always topologize!”
Im Seminar wird ein Skript durchgearbeitet. Die Studierenden präsentieren während der Präsenzsessions den Inhalt des Textes bzw. Lösungen zu Aufgaben zum Text selbständig an der Tafel.
Literatur
- J.-E. Pin: Mathematical Foundations of Automata Theory
- E. Grädel, W. Thomas, T. Wilke: Automata, Logic, and Infinite Games, Springer, 2002
- D. Perrin, J.-E. Pin: Infinite Words, Academic Press, 2004
- H. Straubing: Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, 1994