Proseminar Automatentheorie
» This course is given in German.
Proseminar im Wintersemester 2013/2014
Veranstalter
Lehrstuhl Informatik 7, Christof LödingInhalt
In diesem Proseminar werden weiterführende Themen im Anschluss an die Vorlesung Formale Systeme, Automaten, Prozesse behandelt. Die genaue Auswahl der Themen wird sich nach der Anzahl der Teilnehmer richten. Für Themenbeispiele siehe die Webseite des Proseminars vom letzten Jahr.
Neben der Erarbeitung der Inhalte tritt mit gleichem Gewicht das Training in der Literatur-Recherche, der Strukturierung des Stoffes und der kompetenten Präsentation (schriftlich und im Vortrag).
Organisatorisches
Die Vergabe der Plätze erfolgt über das zentrale Vergabeverfahren.
Informationen zum Ablauf des Proseminars findet man auf den Folien aus der VorbesprechungBei Fragen wenden Sie sich bitte an Christof Löding.
Termine
- Laut Prüfungsordnung haben Sie nach der Vorbesprechung 3 Wochen, um sich vom Seminar abzumelden (ohne einen Fehlversuch angerechnet zu bekommen). Danach wir die Anmeldung verbindlich.
- Die Vorträge des Proseminars werden semesterbegleitend dienstags von 16:15-17:30 Uhr im Seminarraum am Lehrstuhl 7 stattfinden (siehe unten für die Liste der Termine und Themen). Normalerweise finden zwei Vorträge pro Termin statt. Am letzten Termin sind 3 Vorträge geplant.
- Veranstaltung mit Hinweisen zur Ausarbeitung sowie zum Vorbereiten und Halten von Vorträgen in der ersten Vorlesungswoche: Dienstag, 15.10.2013, 16-17 Uhr, Seminarraum Informatik 7. Folien aus der Veranstaltung
- Erste Besprechung mit Betreuer spätestens 6 Wochen vor dem Vortragstermin (Sie müssen sich beim Betreuer melden). Sie sollten sich möglichst früh melden, um abzuklären, wo die Schwerpunkte gesetzt werden sollen.
- Abgabe der Ausarbeitung bis spätestens 2 Wochen vor dem
Vortragstermin (oder nach Absprache mit Betreuer).
Themen
-
Das Komplementproblem für DPDAs
Quelle: [HU79,10.2]
Vortrag: Pascal Stump
Betreuung: S. Repke
-
Ogdens Lemma
Quelle: [Rich,13.6], [HU79,6.1]
Vortrag: Sandra-Jasmin Petrut
Betreuung: S. Repke
-
Greibach Normalform
Quelle: [Rich,11.8,D.1], [Kozen,21]
Vortrag: Eva Fluck
Betreuung: S. Repke
-
Satz von Chomsky und Schützenberger
Quelle:[Kozen,G]
Vortrag: Lukas Huwald
Betreuung: S. Repke
-
Lineare Sprachen
Quelle: [Harrison,6.8]
Vortrag: Sebastian Hueber
Betreuung: M. Lang
-
Mehrdeutige Grammatiken
Quelle: [Rich,11.7], [HU79,4.7]
Vortrag: Julia Barth
Betreuung: M. Lang
-
LR(0)-Grammatiken und DPDAs
Quelle: [HU79,10.6]
Vortrag: entfällt
Betreuung: M. Lang
-
Lindenmayer-Systeme
Quelle: [Rich,24.4]
Vortrag: Christopher Hugenroth
Betreuung: M. Lang
-
Typ-0-Sprachen und Turingmaschinen
Quelle: [Rich,23.1 und 23.2], [HU69,7.5]
Vortrag: Bernd Hankammer
Betreuung: M. Lang
-
Satz von Parikh
Quelle:[Rich,13.7+D.3], [Kozen,H]
Vortrag: Florian Lahr
Betreuung: M. Lang
-
Vier-Wege-Automaten
Quelle: [BH67]
Vortrag: Lukas Westhofen
Betreuung: M. Lang
-
Zwei-Wege-Automaten
Quelle: [HU79,2.6]
Vortrag: David Rath
Betreuung: M. Lang
-
Umformungen für reguläre Ausdrücke
Quelle: [HMU,3.4]
Vortrag: Daniel Schuster
Betreuung: C. Löding
-
Erweiterte Abschlusseigenschaften regulärer Sprachen
(Substitutionen und Homomorphismen)
Quelle: [HU79,3.2], [HMU,4.2.3 und 4.2.4]
Vortrag: Niklas Rieken
Betreuung: C. Löding
-
Co-Determinismus und Minimierung durch Determinisierung
Quelle: [Sakarovitch,3.3.4]
Vortrag: Timon Noethlichs
Betreuung: C. Löding
-
Zustandszusammenfassung für nichtdeterministische Automaten
Quelle: [Kozen,B]
Vortrag: Ömer Sali
Betreuung: C. Löding
-
Automaten mit Gleichungen
Quelle: [KN01]
Vortrag: Lukas Armborst
Betreuung: C. Löding
-
Automaten mit Ausgabe: Einführung und Minimierung
Quelle: [Kohavi,10-1 und 10-3]
Vortrag: Maria Theißen
Betreuung: C. Löding
-
Minimierung unvollständig spezifizierter Automaten mit Ausgabe
Quelle: [Kohavi,10-4] und evtl. [Pfleeger73]
Vortrag: Steffen Fündgens
Betreuung: C. Löding
12. November 2013
19. November 2013
26. November 2013
3. Dezember 2013
10. Dezember 2013
17. Dezember 2013
14. Januar 2014
21. Januar 2014
28. Januar 2014
-
Das Komplementproblem für DPDAs
Quellen
[BH67] | Blum, M./ Hewitt, C.: Automata on a 2-dimensional tape. Proc. 8th IEEE Symp. on Switching and Automata Theory, 155-167, 1967. |
[Harrison] | Harrison, Michael A.: Introduction to Formal Language Theory. Addison-Wesley, 1978. |
[HMU] | Hopcroft, John E. / Motwani, Rajeev / Ullman, Jeffrey D.: Introduction to automata theory, languages, and computation. Addison-Wesley, 2. Auflage, 2001. |
[HU69] | Hopcroft, John E. / Ullman, Jeffrey D.: Formal Languages and their Relation to Automata. Addison-Wesley, 1969. |
[HU79] | Hopcroft, John E. / Ullman, Jeffrey D.: Introduction to automata theory, languages, and computation. Addison-Wesley, 1979. |
[Kohavi] | Kohavi, Zvi: Switching and Finite Automata Theory. McGraw-Hill 1970. |
[KN01] | Khoussainov, Bakhadyr/ Nerode, Anil: Automata Theory and its Applications Birkhäuser 2001. |
[Kozen] | Kozen, Dexter: Automata and Computability. Springer 1997. |
[MKA] | Skript zur Vorlesung Modelle und Konstruktionen der Automatentheorie, W. Thomas, 1999. Link |
[Pfleeger73] | Pfleeger, Charles P.: State Reduction in Incompletely Specified Finite-State Machines. IEEE Transactions on Computers, vol. C-22(12), 1973, pp. 87--106, 1973. |
[Rich] | Rich, Elaine: Automata, computability, and complexity - Theory and applications. Pearson, 2008. |
[Sakarovitch] | Sakarovitch, Jacques: Elements of Automata Theory. Cambridge University Press, 2009. |