Sommersemester 2021: 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–25 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 (s.u.) können Sie Folien live annotieren. Nutzen Sie diese Option, falls sie sich für Ihren Vortrag anbietet.
• 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.
  • 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

• Betreuungen sowie Vorträge finden online statt
• Die Vorträge finden 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 in verschiedene Automatenmodelle. Die Themen sind diversen Quellen entnommen.
Einige Quellen sind nicht öffentlich zugänglichen und daher passwortgeschützt hinterlegt. Das Passwort ist im AlmaWeb zu finden.
Die Themenvergabe wird nach Windhundverfahren über ein >Dudle (Bachelor) [link] (bis 22. April 12:00) organisiert.

Nr.	Thema	Quelle und Details	Name	Termin	Betreuer
01	Unendliche Worte und Büchi-Automaten	Abschnitte 1.1, 1.2, 1.3.1 in Automata, Logics, and Infinite Games (Passwort siehe AlmaWeb)	Lukas Göhlich	20.05.	Arndt
02	Muller-, Rabin- und Streett-Automaten und die Äquivalenz der Modelle	Abschnitte 1.3.2, 1.3.3 in Automata, Logics, and Infinite Games (Passwort siehe AlmaWeb)
03	Bäume und Baumautomaten	Abschnitt 1.1 in Tree Automata: Techniques and Applications	Maximus Germer	20.05.	Arndt
04	Pumping Lemma und Abschlusseigenschaften regulärer Baumsprachen	Abschnitte 1.2, 1.3 in Tree Automata: Techniques and Applications	Kai Knappik	27.05.	Arndt
05	Myhill-Nerode für reguläre Baumsprachen und Minimierung von Baumautomaten	Abschnitt 1.5 in Tree Automata: Techniques and Applications	Thomas Abel	27.05.	Arndt
06	Blattsprachen regulärer Baumsprachen	Abschnitt 2.4 in Tree Automata: Techniques and Applications
07	Schachtelworte und Schachtelwortautomaten	Abschnitte 2, 3.1, 3.2 in Adding Nesting Structure to Words	Manh Le	03.06.	Tronicke
08	Determinisierung von Schachtelwortautomaten	Abschnitt 3.3 in Adding Nesting Structure to Words	Till Schultz	08.07.	Tronicke
09	Bildsprachen und Vier-Wege-Automaten	Abschnitte 2, 4.1 in Two-dimensional languages	Wakiya Schulz	10.06.	Ruge
10	Bildgrammatiken	Abschnitt 5 in Two-dimensional languages	Jakob Eschrich	10.06.	Ruge
11	Parkettierungssysteme für Bildsprachen	Abschnitte 7.1, 7.2, 7.3 in Two-dimensional languages
12	Unentscheidbarkeit des Leehrheitsproblems für Parkettierungssysteme	Abschnitt 9.2 in Two-dimensional languages
13	Graphautomaten	Abschnitte 2.1, 2.2 in Nondeterminism versus Determinism of Finite Automata over Directed Acyclic Graphs
14	Nichtdeterminisierbarkeit von Graphautomaten	Abschnitt 3 in Nondeterminism versus Determinism of Finite Automata over Directed Acyclic Graphs
15	Abschlusseigenschaften regulärer DAG-Sprachen	Abschnitte 2, 3 in Language theoretic properties of regular DAG languages
16	Endliche Übersetzer	Lecture Notes: Finite State Transducers	Cuong Vo Ta	24.06.	Tronicke
17	Moore- und Mealy-Automaten	Abschnitt 2.7 (S. 42–44) in Introduction to Automata Theory, Languages, and Computation (Passwort siehe AlmaWeb)	Daniel Grohmann	01.07.	Ruge
18	Zwei-Wege-Automaten und die Äquivalenz zu endlichen Automaten	A Note on the Reduction of Two-Way Automata to One-Way Automata	Michael Schmidt	01.07.	Ruge
19	Automaten auf unendlichen Bäumen	Abschnitt 6.1 in Automata, Logic and Games
20	Nichtdeterminisierbarkeit von Max-Plus-Automaten	Abschnitte 2.4, 3.1 in Deciding Unambiguity and Sequentiality starting from a Finitely Ambiguous Max-Plus Automaton

Seminarmodul Master

Für das Seminarmodul im Master stehen die folgenden Themen zur Auswahl. Abgesehen von Themen 10 und 11 sind alle Themen unabhängig voneinander, die Gruppierung dient nur der Übersichtlichkeit.
Die Themenvergabe wird nach Windhundverfahren über ein >Dudle (Master) [link] (bis 22. April 12:00) organisiert.

Nr.	Thema	Quelle und Details	Name	Termin	Betreuer
01	Determinisation of ω-automata	Kapitel 1 in An Automata Toolbox (Passwort siehe AlmaWeb)	Jonatan Bleicher	21.07.	Grabolle
02	Infinite duration games	Kapitel 2 in An Automata Toolbox (Passwort siehe AlmaWeb)
03	Two-way transducers	Kapitel 13 in An Automata Toolbox (Passwort siehe AlmaWeb)	Stefan Härtel	30.06.	Grabolle
04	Streaming string transducers	Kapitel 14 in An Automata Toolbox (Passwort siehe AlmaWeb)	Georg Walther	28.07. 10:15	Grabolle
05	Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring	Link
06	Series which are both max-plus and min-plus rational are unambiguous	Link	Bastian Grahm	26.05.	Paul
07	Parikh's Theorem: A simple and direct automaton construction	Link
08	On the degree of ambiguity of finite automata	Abschnitte 2, 3, evtl. 4 in Link	Lena Gladbach	22.07. 11:15	Paul
09	The Support of a Recognizable Series over a Zero-Sum Free, Commutative Semiring is Recognizable	Link	Egor Morozov	07.07.	Paul
10	A context-freeness lemma for hyperedge replacement grammars and languages	Abschnitt 2.3 in Hyperedge Replacement Graph Grammars
11	Structural properties and generative power of hyperedge replacement languages and grammars	Abschnitte 2.4, 2.5 in Hyperedge Replacement Graph Grammars