Proseminar Automatentheorie

» This course is given in German.

Proseminar im Wintersemester 2010/2011

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 als auch allgemeinerer Objekte wie Pixel-Bildern.

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

Informationen zum Ablauf des Proseminars findet man auf den Folien aus der Vorbesprechung

Die Vergabe der Plätze ist über das zentrale Vergabeverfahren erfolgt. Es sind alle Plätze belegt.

Das Proseminar wird als Blockveranstaltung an folgenden Terminen durchgeführt:

  • Mittwoch, 12.1.2011, von 14:30 bis ca. 16:15 Uhr (3 Vorträge)
  • Dienstag, 18.1.2011, von 14 bis ca. 16:30 Uhr (4 Vorträge)
voraussichtlich an zwei Tagen während der Vorlesungszeit.

Termine

  • Am 13.10.2010 findet um 15 Uhr im Seminarraum am Lehrstuhl 7 eine Veranstaltung zum Vorbereiten und Gestalten von Vorträgen statt. Folien aus der Veranstaltung
  • Bis spätestens zum 22.10.2010 müssen Sie sich mit Ihrem Betreuer für eine erste Absprache zu den Inhalten getroffen haben.
  • Abgabe der Ausarbeitung bis spätestens zum 21.12.2010 (oder nach Absprache mit Betreuer).

Vorträge am Mittwoch, 12.1.2011:

  1. Ogdens Lemma
    Quelle: [Rich,13.6]
    Vortrag: Matthias Hoelzel
    Betreuung: C. Löding
  2. Kontextsensitive Sprachen und linear beschränkte Automaten
    Quelle: [Rich,24.1]
    Vortrag: Bertina Amy Linnes
    Betreuung: C. Löding
  3. Lindenmayer-Systeme
    Quelle: [Rich,24.4]
    Vortrag: Stefan Schubert
    Betreuung: J. Olschewski

Vorträge am Dienstag, 18.1.2011:

  1. Endliche Automaten mit Ausgabe
    Quelle: [HU79,2.7], [Kohavi,10-3]
    Vortrag: Nils Kramer
    Betreuung: J. Olschewski
  2. Vier-Wege-Automaten
    Quelle: [BH67]
    Vortrag: Rafael Przybylski
    Betreuung: W. Fridman
  3. Baumautomaten
    Quelle: [GS97,Abschnitt 5], [AAT, Kapitel 3]
    Vortrag: Hendrik Wansing
    Betreuung: W. Thomas
  4. Reguläre Baumgrammatiken und Ableitungsbäume
    Quelle: [GS97,Abschnitte 6,14]
    Vortrag: Florian Richter
    Betreuung: W. Thomas

Quellen

[AAT] Skript zur Vorlesung Applied Automata Theory bzw. Angewandte Automatentheorie, W. Thomas, 2005. Link
[BH67] M. Blum, C. Hewitt.: Automata on a 2-dimensional tape. Proc. 8th IEEE Symp. on Switching and Automata Theory, 155-167, 1967.
[GS97] F. Gescseg, M. Steinby: Tree Languages.In Handbook of Formal Languages, G. Rosenberg and A. Salomaa (Eds), Vol. III, Kapitel 1, Springer Verlag, 1997.
[Harrison] Harrison, Michael A.: Introduction to Formal Language Theory. Addison-Wesley, 1978.
[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.
[Rich] Rich, Elaine: Automata, computability, and complexity - Theory and applications. Pearson, 2008.