Proseminar Automatentheorie

» This course is given in German.

Proseminar im Wintersemester 2011/2012

ArtTermine/OrtBeginnVeranstalter
PS2 Termine nach Vereinbarung Thomas

Inhalt

In diesem Proseminar werden weiterführende Themen im Anschluss an die Vorlesung Formale Systeme, Automaten, Prozesse behandelt. Es geht beispielsweise um erweiterte Modelle von Automaten für die Beschreibung von Wörtern (z.B. Zweiwege-Automaten) als auch allgemeinerer Objekte wie zweidimensionale Gitterstrukturen.

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 Vorbesprechung

Termine

  • Am Montag, den 8.10.2010 findet um 14 Uhr im Seminarraum am Lehrstuhl 1 (der Raum wurde geändert) eine Veranstaltung zum Vorbereiten und Gestalten von Vorträgen statt. Folien aus der Veranstaltung
  • Bis spätestens zum 19.10.2010 müssen Sie sich mit Ihrem Betreuer für eine erste Absprache zu den Inhalten getroffen haben. Wenn Sie einen der ersten Vortragstermine haben, dann sollten Sie sich früher beim Betreuer melden.
  • Abgabe der Ausarbeitung bis spätestens 3 Wochen vor dem Vortragstermin (oder nach Absprache mit Betreuer).
  • Die Vorträge des Proseminars werden an 7 Terminen jeweils dienstags von 16-17:30 Uhr mit je 3 Vorträgen pro Termin ab dem 20. November im Seminarraum am Lehrstuhl 7 stattfinden.

Themen

    20. November 2012
  1. Zwei-Wege-Automaten
    Quelle: [HU79,2.6]
    Vortrag: Ahmet Altinbüken
    Betreuung: W. Thomas
  2. Vier-Wege-Automaten
    Quelle: [BH67]
    Vortrag: Niklas Reinker
    Betreuung: W. Thomas
  3. Automatendefinierbare Relationen
    Quelle: [MKA,4.2-4.4]
    Vortrag: Julia Lenzen
    Betreuung: W. Thomas

    4. 27. November 2012
  4. Keine Vorträge: Termin entfällt

    5. 11. Dezember 2012
  5. Greibach Normalform
    Quelle: [Rich,11.8,D.1], [Kozen,21]
    Vortrag: Amadeus Garus
    Betreuung: W. Thomas
  6. Satz von Chomsky und Schützenberger
    Quelle:[Kozen,G]
    Vortrag: Hongmei Liang
    Betreuung: W. Thomas
  7. Mehrdeutige Grammatiken
    Quelle: [Rich,11.7], [HU79,4.7]
    Vortrag: Tobias Jansen
    Betreuung: D. Neider

    8. 18. Dezember
  8. Lindenmayer-Systeme
    Quelle: [Rich,24.4]
    Vortrag: entfällt
    Betreuung: D. Neider
  9. Typ-0-Sprachen und Turingmaschinen
    Quelle: [Rich,23.1 und 23.2], [HU69,7.5]
    Vortrag: Florian Lammers
    Betreuung: D. Neider
  10. Satz von Parikh
    Quelle:[Rich,13.7+D.3], [Kozen,H]
    Vortrag: Alexander Engbrecht
    Betreuung: D. Neider

    11. 8. Januar 2013
  11. Umformungen für reguläre Ausdrücke
    Quelle: [HMU,3.4]
    Vortrag: Jonathan Liebig
    Betreuung: D. Neider
  12. Erweiterte Abschlusseigenschaften regulärer Sprachen (Substitutionen und Homomorphismen)
    Quelle: [HU79,3.2], [HMU,4.2.3 und 4.2.4]
    Vortrag: David Schmalzing
    Betreuung: D. Neider
  13. Co-Determinismus und Minimierung durch Determinisierung
    Quelle: [Sakarovitch,3.3.4]
    Vortrag: Stefan Meeger
    Betreuung: D. Neider

    14. 15. Januar 2013
  14. Automaten mit Ausgabe: Einführung und Minimierung
    Quelle: [Kohavi,10-1 und 10-3]
    Vortrag: Esra Türk
    Betreuung: C. Löding
  15. Minimierung unvollständig spezifizierter Automaten mit Ausgabe
    Quelle: [Kohavi,10-4] und evtl. [Pfleeger73]
    Vortrag: Niklas Scholz
    Betreuung: C. Löding
  16. Homing- und Synchronizations-Experimente
    Quelle: [Kohavi,13-1 und 13-2]
    Vortrag: Yannick Deuster
    Betreuung: C. Löding

    17. 22. Januar 2013
  17. Diagnostizierbare Automaten mit Ausgabe
    Quelle: [Kohavi,13-6]
    Vortrag: Benedikt Röder
    Betreuung: C. Löding
  18. Speicherspannweite in Automaten mit Ausgabe
    Quelle: [Kohavi,14-1]
    Vortrag: Stahlmann Stephan
    Betreuung: C. Löding
  19. Verlustfreie Automaten mit Ausgabe
    Quelle: [Kohavi,14-4]
    Vortrag: Hilke Buss
    Betreuung: C. Löding

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.
[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.