Seminar über Automatentheorie (omega-Automaten und verwandte Themen)

» This course is given in German.

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, mit einem Schwerpunkt im Umkreis der Vorlesung Infinite Computations des WS 2010/11. 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.

Ablauf und Termine

  • Allgemeine Informationen zum Ablauf findet man auf den Folien aus der Vorbesprechung
  • Das Seminar wird in zwei Blöcken zum Ende der Vorlesungszeit stattfinden.
  • Folgende Termine sind neben den Vortragsterminen einzuhalten:
    • Erste Absprache mit dem Betreuer bis spätestens 15.4.2010
    • Abgabe der Ausarbeitung: bis zum 10.6.2011
  • Die Vorträge finden im Seminarraum am Lehrstuhl 7 am 8.7. und am 15.7.2011 statt. Die Zeiten sind bei den Vorträgen eingetragen.

Bei Fragen wenden Sie sich bitte an Christof Löding.

Vorträge

Freitag, 8.7.2011

  • 9:00-10:00 Uhr: Erkennbare Tracesprachen
    Quelle: Kapitel 6.1-6.3 aus [DR95]
    Vortrag: Christian Kuknat
    Betreuung: W. Fridman, W. Thomas
  • 10:15-11:15 Uhr: Asynchrone Automaten
    Quelle: Kap 2.4 aus [Die90]
    Vortrag: Karolin Köhler
    Betreuung: N. Chaturvedi, W. Thomas
  • 11:30-12:30 Uhr: Universalautomat I - Definition und Eigenschaften
    Quelle: [LS07]
    Vortrag: Benjamin Grap
    Betreuung: C. Löding
  • 14:00-15:00 Uhr: Universalautomat II - Konstruktion und NEA-Minimierung
    Quelle: [LS07]
    Vortrag: Jennifer Lierenfeld
    Betreuung: C. Löding

Freitag, 15.7.2011

  • 9:00-10:00 Uhr: Eingabegesteuerte Kellerautomaten auf endlichen Wörtern
    Quelle: [AM04]
    Vortrag: Dirk Hauptmann
    Betreuung: S. Schulz
  • 10:15-11:15 Uhr: Minimierung von omega-Automaten
    Quellen: [Löd01,Sch10]
    Vortrag: Simon Tenbusch
    Betreuung: M. Gelderie
  • 11:30-12:30 Uhr: Schnell wachsende berechenbare Funktionen
    Quellen: Kap. C.II aus [Bör86]; Kap. 10,11 aus [Pét67]; [Cai07]
    Vortrag: Florian Richter
    Betreuung: F. Radmacher, W. Thomas

Quellen

[AHU74] Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
[AM04] Rajeev Alur, P. Madhusudan. Visibly pushdown languages In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 202-211, ACM 2004.
[BC04] Jean Berstel, Olivier Carton. On the Complexity of Hopcroft's State Minimization Algorithm. In Implementation and Application of Automata, 9th International Conference, CIAA 2004. Lecture Notes in Computer Science 3317, pp. 35.44, Springer 2004.
[Bör86] Egon Börger. Berechenbarkeit, Komplexität, Logik. 2. Aufl., Vieweg 1986.
[Cai07] Andrés Eduardo Caicedo. Goodstein's Function. Revista Colombiana de Matemáticas, 41(2):381-391, 2007.
[DR95] Volker Diekert, Grzegorz Rozenberg (Hrsg.). The book of traces. World Scientific, 1995.
[Die90] Volker Diekert. Combinatorics on Traces. Lecture Notes in Computer Science 454, Springer 1990.
[Löd01] C. Löding. Efficient minimization of deterministic weak omega-automata. Information Processing Letters, 79(3):105-109, 2001.
[LMS04] Christof Löding, P. Madhusudan, and Olivier Serre. Visibly pushdown games. In Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2004, volume 3328 of Lecture Notes in Computer Science, pages 408-420. Springer, 2004.
[LS07] Sylvain Lombardy, Jacques Sakarovitch. The universal automaton. Logic and automata: History and Perspectives, Amsterdam University Press, pages 457--504, 2007
[Pét67] Róza Péter. Recursive Functions. 3. Aufl., Academic Press 1967.
[Sch10] Sven Schewe. Beyond Hyper-Minimisation - Minimising DBAs and DPAs is NP-Complete. In Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, LIPIcs 8 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2010.