Logic and
Theory of
Discrete Systems

Informatik 7


Proseminar über Automatentheorie (Wintersemester 2015/16)

Inhalt

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.

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.

Die Vorbesprechung wird am Freitag, den 7.8.2015, um 11 Uhr im Seminarraum des Lehrstuhls Informatik 7 stattfinden (Informatikzentrum, Gebäudeteil E1, 1.OG Raumnummer 4116). Die Vorbesprechung dient der Themenauswahl und der zur Besprechung der allgemeinen Seminarorganisation.

Das Seminar wird an 5 Terminen jeweils Mittwochs im Zeitraum von 15 Uhr bis 17:30 stattfinden. Der erste Termin ist der 11.11.. Der Raum wird im Laufe des Semesters bekannt gegeben.

Die Folien aus der Einführung in Latex gibt es hier sowie die Templates ausarbeitung.texausarbeitung.bib und praesentation.tex.

Die Folien der Einführungsveranstaltung zum Thema "Wie halte ich einen Vortrag?" gibt es hier, die Folien zur Ausarbeitung gibt es hier.

Bei Fragen wenden Sie sich bitte an Martin Lang.

Themen- und Terminverteilung

  1. Termin 11.11. 15 Uhr bis 17 Uhr (Seminarraum i7, Raum 4116)
    • Deterministische 2-Wege-Automaten
      Vortrag:  Kaltwasser
    • Baumautomaten: Definition und Abschlusseigenschaften
      Vortrag: Bayer, J.
    • Baumautomaten: Algorithmen (Nichtleerheit, Äquivalenz, Minimierung)
      Vortrag: Bayer, P.
  2. Termin 18.11. 15 Uhr bis 17 Uhr (Seminarraum i7, Raum 4116)
    • 4-Wege-Automaten auf Gittern: Definition und Mächtigkeit
      Vortrag: Roersch
    • 4-Wege-Automaten mit Markern
      Vortrag: Holmes
    • Parkettierungssysteme auf Gittern: Definition und Mächtigkeit
      Vortrag: Heyen
    • Parkettierungssysteme auf Gittern: Komplexität und Unentscheidbarkeit
      Vortrag: Ohn
  3. Termin 25.11. 15 Uhr bis 17 Uhr (Seminarraum i7, Raum 4116)
    • Progressive Gitterautomaten: Definition und Mächtigkeit
      Vortrag: Jörres
    • Reguläre Sprachen über dem Alphabet {a}: Semilineare Mengen
      Vortrag: Kettel
    • Der Satz von Parikh
      Vortrag: Mutert
  4. Termin 02.12. 15 Uhr bis 17 Uhr (Seminarraum i7, Raum 4116)
    • Greibach-Normalform für kontextfreie Grammatiken: Beweis von Paull
      Vortrag: Rehbold
    • Greibach-Normalform: Beweis von Kozen
      Vortrag: Reinartz
    • Deterministische Pushdown-Automaten: Komplementierung
      Vortrag: Böcker
  5. Termin 09.11. 15 Uhr bis 17 Uhr (Seminarraum i3, 3. OG E1)
    • Klammer-Sprachen
      Vortrag: Al Enezy
    • Lineare Sprachen
      Vortrag: Lu
FaLang translation system by Faboba