Wintersemester 2021/22: Seminarmodul Automatentheorie (Bachelor & Master)

Bei Fragen wenden Sie sich bitte an Erik Paul.

Aufgabenstellung

Details

Besprechung mit Betreuer

Durchführung

Seminarmodul Bachelor

Inhaltlich verfolgt das Seminar in diesem Semester eine Einführung verschiedene Grundlagenthemen der Automaten- und formalen Sprachtheorie.
Die Themen sind Abschnitte aus dem Buch "Automata, Languages, and Machines – Volume A" von Samuel Eilenberg. Das Passwort ist im AlmaWeb zu finden.
Betreuungen werden anhand der Themengruppierungen wie unten gebündelt.
Die Themenvergabe wird nach Windhundverfahren über ein Dudle (Bachelor) [link] (bis 25. Oktober 10:00) organisiert.
Nr.KapitelInhaltNameTerminBetreuer
01 II.1 – II.3 Einführung und Abschlusseigenschaften Florian Speer 25.11. Arndt
02 II.4 – II.6 Erreichbarkeit, Endlichkeit und lokale Mengen Friedrich Schwella 25.11. Arndt
03 III.1 – III.3 Deterministische Automaten und Divisionskalkül Marvin Polster 07.12. 11:15 Arndt
04 III.4 Zustandsabbildungen Leonhard Kepser 07.12. 11:15 Arndt
05 III.5 Minimalautomaten Mel Tellermann 07.12. 11:15 Arndt
06 III.8 + III.9 Quotientenkriterium und Rechtskongruenzen Felix Seidl (?) 09.12. Ruge
07 III.10 + III.11 Syntaktische Monoide
08 IV.1 + IV.2 Unitäre Mengen und Präfixe Johanna Soest 16.12. Arndt
09 IV.3 + IV.4 Unitäre Monoide und Dekompositionsalgorithmus Felix Diez 16.12. Arndt
10 IV.5 + IV.6 Basen unitärer Monoide und iterierte UP-Dekomposition Max Martin Freiberg 06.01. Arndt
11 IV.7 + IV.8 Maximale Präfixe und rekurrente Mengen Kai Lanzendorf 06.01. Arndt
12 V.1 + V.2 Der Monoid ℕ und Zahlen zur Basis k
13 V.3 + V.4 k-Erkennbare Mengen und Iteration Jonathan Schneider 13.01. Ruge
14 V.5 – V.7 Lückentheoreme
15 VI.1 + VI.2 Vielfachheit und Halbringe (K)
16 VI.3 + VI.4 K-Teilmengen, Relationen und Funktionen Paul Bachmann 13.01. Tronicke
17 VI.5 + VI.6 Monoide, Matrizen und K-Σ-Automaten
18 VI.7 + VI.8 Erkennbare K-Teilmengen und der Gleichheitssatz
19 VI.9 + VI.10 Der Fall K = ℕ und der Divisionssatz
20 VI.11 + VI.12 Der Subtraktionssatz und Unentscheidbarkeiten
21 VII.1 + VII.2 +-Algebren und rationale K-Teilmengen Mose Schmiedel 20.01. Ruge
22 VII.3 + VII.4 Rationale Ausdrücke, Identitäten und lokal endliche Monoide Finn Hoffmann 20.01. Ruge
23 VII.5 Der Satz von Kleene Ziyad Nuwayhid 20.01. Ruge
24 IX.1 + IX.2 Rationale Relationen und Erster Faktorisierungssatz Marvin Großer 27.01. Tronicke
25 IX.3 + IX.4 Auswertungssatz und Kompositionssatz
26 IX.5 Zweiter Faktorisierungssatz
27 X.1 + X.2 Maschinen Erik Rötschke 27.01. Tronicke
28 X.8 + X.9 Deterministische Maschinen
29 XIII.1 + XIII.2 Unendliche Worte und schließlich periodische Folgen Nils Oskar Nuernbergk 03.02. Ruge
30 XIII.3 + XIII.4 Darstellungen reeller Zahlen
31 XIII.5 + XIII.6 Die Peano-Kurve und die Hilbert-Kurve Lucas Zetzsche 03.02. Ruge

Seminarmodul Master

Für das Seminarmodul im Master stehen die folgenden Themen zur Auswahl.
Die Themenvergabe wird nach Windhundverfahren über ein Dudle (Master) [link] (bis 25. Oktober 10:00) organisiert.
Nr.ThemaQuelle und DetailsNameTerminBetreuer
01 Infinite duration games Kapitel 2 in An Automata Toolbox (Passwort siehe AlmaWeb)
02 A context-freeness lemma for hyperedge replacement grammars and languages Abschnitt 2.3 in Hyperedge Replacement Graph Grammars
03 Structural properties and generative power of hyperedge replacement languages and grammars Abschnitte 2.4, 2.5 in Hyperedge Replacement Graph Grammars
04 Two-way finite state transducer Kapitel 2 in Link
05 Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring Link Silja Ava Schirmer 07.12. 9:15 Paul
06 Pumping lemmas for weighted automata Link
07 An algebraic characterization of semirings for which the support of every recognizable series is recognizable Link Alexander Vödisch 16.12. Paul
08 Nondeterminism versus determinism of finite automata over directed acyclic graphs Link Jonas Irmler 06.01. Paul
09 Parikh's Theorem: A simple and direct automaton construction Link Dominik Ebach 18.01. 9:15 Paul
10 Unambiguous recognizable two-dimensional languages Link Tobias Wawrik 27.01. Paul
Probabilistische Automaten:
11 Einführung und Vergleich mit regulären Sprachen Einführung und Abschnitt 1.1.1 in Link, Kapitel I–IV in Probabilistic automata Marcus Stuber 09.12. Nasz
12 Universell nicht-reguläre Probabilistische Automaten, Motivation Isolierter Cut-Points Abschnitt 1.1.2 in Link, Kapitel V in Probabilistic automata, Abschnitte 2–3 in Link
13 Reduktionstheorem und Saving of States, Operationen auf Probabilistischen Automaten Abschnitte 1.1.3 und 1.2 in Link, Kapitel VI–VII in Probabilistic automata
14 (Un-)Entscheidbarkeiten, darunter Isolation Problem und Value 1 Problem Abschnitte 1.4 und 1.5 in Link, Link Maximilian Zimmer 03.02. Nasz