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

Bei Fragen wenden Sie sich bitte an Erik Paul.

Aufgabenstellung

• Ihre Aufgabe im Rahmen des Seminarmoduls ist es, den erhaltenen bzw. ausgewählten Text gründlich durchzuarbeiten und im Rahmen eines Vortrages vorzustellen.
• Der Vortrag soll im Seminarmodul Bachelor eine Dauer von 20 Minuten, im Seminarmodul Master eine Dauer von 45–50 Minuten haben.
• Sie erhalten einen Betreuer, mit dem inhaltliche sowie gestalterische Fragen geklärt werden können.
  Es wird erwartet, dass Sie sowohl den Inhalt als auch das Präsentationskonzept des Vortrags mit Ihrem Betreuer besprechen.
• Nach jedem Vortrag gibt es eine Fragerunde. Jede·r Teilnehmer·in soll mindestens bei ca. jedem zweiten Termin eine Frage stellen.
• Eine schriftliche Ausarbeitung wird nicht erwartet.

Details

• Es wird i.A. nicht möglich sein, alle Details des erhaltenen Themas vorzustellen. Teil der Aufgabenstellung ist es daher, für den Vortrag eine geeignete inhaltliche Auswahl zu finden.
  Hierbei kann es auch sinnvoll sein, sich mit den Studierenden auszutauschen, die ein zusammenhängendes Thema bearbeiten.
• Der Vortrag sollte visuell unterstützt werden, z.B. durch Beamer-Folien.
  Einige Hinweise zur Erstellung von Folien:
  • Zu allem was Sie sagen, sollte ein Stichpunkt auf den Folien sein, an denen sich der Hörer "festhalten" kann. Andererseits sollten Sie zu allem sprechen, was sich auf den Folien befindet.
    Inhalte, die "nur der Vollständigkeit halber" aufgeführt sind, sollten ganz verschwinden.
  • Nutzen Sie Text sparsam. Folien sollen Sie unterstützen, nicht Sie ersetzen. Auf vollständige Sätze sollte verzichtet werden, Verben und Artikel sind meist auch überflüssig.
  • Eine Folie sollte nicht mehr als 10–11 Zeilen Text beinhalten, sonst leidet die Übersichtlichkeit.
  • Zeilenumbrüche stören den Gedankenfluss.
  • Nutzen Sie Farben, z.B. zur Hervorhebung wichtiger Inhalte, zur Gliederung oder um Unterschiede bzw. Gemeinsamkeiten zu kennzeichnen. Fette und kursive Schriften sind kein geeignetes Mittel um Inhalte auf Folien hervorzuheben.
  • Nutzen Sie Abbildungen wenn möglich, diese gehen schnell ins Gehirn.
  • Nutzen Sie Formeln nur, wenn es sein muss. Diese sind für den Hörer schwer zu verarbeiten, lassen Sie hierfür dementsprechend auch genügend Zeit.
  • In BigBlueButton können Sie Folien live annotieren. Nutzen Sie diese Option, falls sie sich für Ihren Vortrag anbietet.
  • Bei einem Präsenzvortrag kann ein zweiter Beamer oder ein Polylux verwendet werden, um Inhalte vorhergehender Folien festzuhalten.
• Jeder Vortrag sollte einen Beweis beinhalten. Im Bachelor sollte wegen der kurzen Dauer der Vorträge allerdings ein eher einfacher Beweis gewält werden oder, im Idealfall, die grobe Beweisidee eines komplexeren Beweises.
  Dies hängt natürlich auch davon ab, welche Art von Beweisen das bearbeitete Thema enthält.
• Zu jedem wissenschaftlichen Vortrag gehören Fragen und eine wissenschaftliche Diskussion. Die Erwartung Ihrer Fragen soll Sie an dies heranführen. Alle auf den Vortrag bezogenen Fragen sind zugelassen, auch reine Verständnisfragen.
• Vortragssprache ist Deutsch oder Englisch (freie Wahl)

Besprechung mit Betreuer

• Ohne die Wahrnehmung der folgenden Pflichttermine kann keine Bewertung unsererseits stattfinden.
  • Drei Wochen vor dem Vortrag hat zur inhaltlichen Besprechung ein Termin mit dem Betreuer stattzufinden. Hierbei ist zu beachten, dass im Wintersemester die freien Tage über Weihnachten als 0 Tage gezählt werden.
  • Zwei Wochen vor dem Vortrag ist das Präsentationskonzept, insbesondere die Vortragsfolien, mit dem Betreuer zu besprechen.
• Abgesehen von diesen Terminen können natürlich auch weitere bzw. frühere Termine vereinbart werden.

Durchführung

• Die Vorträge finden online statt als BigBlueButton-Konferenz im RocketChat-Kanal des Seminars (Link siehe AlmaWeb).
  Den Konferenz-Raum finden Sie im Chat-Kanal durch Klicken auf den Telefonhörer rechts oben. Mach dem Beitritt der Konferenz können Sie das kleine Popup-Fenster über ein Aufklapp-Menü rechts oben maximieren.
• Sie können RocketChat auch nutzen, um einen privaten BBB-Raum zu erstellen (links bei Direktnachrichten unter Ihrem eigenen Namen) und sich mit den Raumfunktionen vertraut zu machen.
• Während eines Vortrags sollen alle Zuhörer·innen ihre Kamera aus und ihr Mikrophon stumm schalten.
• Die/der Vortragende soll eine Kamera ("Facecam") verwenden.

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.	Kapitel	Inhalt	Name	Termin	Betreuer
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.	Thema	Quelle und Details	Name	Termin	Betreuer
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