Logic and
Theory of
Discrete Systems

Informatik 7

Seminar über Automatentheorie (Wintersemester 2015/16)

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesung Applied Automata Theory). Aktive Teilnahme an dieser Vorlesung (oder vergleichbaren Vorlesungen in früheren Semestern) inklusive Übung ist hilfreich zur Bearbeitung der Themen und wird bei der Zuteilung von Plätzen berücksichtigt.

Es handelt sich um ein Seminar in der theoretischen Informatik. Es wird entsprechend von den Teilnehmern der Umgang mit abstrakten Modellen und mathematischen Beweisen erwartet.

Bei Fragen wenden Sie sich an Martin Lang.

 

Themen- und Terminverteilung:

  1. Termin 16.11. 13:30 Uhr bis 15:30 Uhr (Seminarraum i7, Raum 4116)
    • Properties and Complementation of DPDAs
      Vortrag: Rajbhandary, Hethnawi

  2. Termin 23.11. 13:30 Uhr bis 15:30 Uhr (Seminarraum i7, Raum 4116)
    • Komplexität der Übersetzung von MSO in endliche Automaten
      Vortrag: Tolksdorf

    • Monadische TC-Logik über Wörtern
      Vortrag: VanLoo

  3. Termin 30.11. 13:30 Uhr bis 15:30 Uhr (Seminarraum i7, Raum 4116)
    • Tilingsysteme und EMSO
      Vortrag: Gilbert

    • 4-Wege-Automaten und monadische TC-Logik über Graphen
      Vortrag: Nowak

  4. Termin 07.12. 13:30 Uhr bis 15:30 Uhr (Seminarraum i7, Raum 4116)
    • Automaten mit Transitionsformeln
      Vortrag: Hoppen

    • Komplementierung von kontextsensitiven Sprachen
      Vortrag: Froitzheim

  5. Termin 14.12. 13:30 Uhr bis 15:30 Uhr (Seminarraum i7, Raum 4116)
    • Registerautomaten (auf unendlichen Alphabeten)
      Vortrag: Bruenjes

    • Automaten für Progressive Grid Walking
      Vortrag: Zimmermann

  6. Termin 11.01. 13:30 Uhr bis 15:30 Uhr (Seminarraum i7, Raum 4116)
    • Aktives Lernen nach Kearns/Vazirani
      Vortrag: Kotenko

    • Abstände zwischen automatendefinierbaren Sprachen
      Vortrag: Klein-Ridder