Seminar über Automatentheorie

» Diese Veranstaltung wird auf deutsch gehalten.

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesung Infinite Computations des WS 2012/13 (die Themen werden in Abhängigkeit der Vorkenntnisse der Teilnehmer evtl. angepasst auf das Umfeld der Vorlesung Angewandte Automatentheorie). 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.

Ablauf und Termine

  • Allgemeine Informationen zum Ablauf findet man auf den Folien aus der Vorbesprechung
  • Die Vorträge werden jeweils in Zweierblöcken zu einem wöchtenlichen Termin in der zweiten Hälfte der Vorlesungszeit stattfinden. Der wöchtenliche Termin wird in Absprache mit den Teilnehmern festgelegt.
  • Folgende Termine sind neben den Vortragsterminen einzuhalten:
    • Erste Absprache mit dem Betreuer bis spätestens 19.4.2013
    • Abgabe der Ausarbeitung: spätestens 3 Wochen vor dem Vortrag

Das Seminar wird angeboten von Christof Löding.

Themen


    Dienstag, 2.7.2013, 16-18 Uhr

  1. Determinisierung von Wort-Transducern (B/M)
    Quelle: [Moh97]
    Vortrag: Alexander Arseniev
    Betreuung: Christof Löding
  2. Minimierung von Wort-Transducern (B/M)
    Quelle: [Moh00]
    Vortrag: entfällt
    Betreuung: Christof Löding

  3. Dienstag, 9.7.2013, 16-18 Uhr

  4. Äquivalenztest für eindeutige NEAs (B/M)
    Quelle: [SH85]
    Vortrag: Niels Bruhn
    Betreuung: Christof Löding
  5. Residuum-Automaten (B)
    Quelle: [DLT01]
    Vortrag: entfällt
    Betreuung: Benedikt Brütsch

  6. Dienstag, 16.7.2013, 16-18 Uhr

  7. Der universelle Automat (B/M)
    Quelle: [LS08]
    Vortrag: Matthias Hölzel
    Betreuung: Stefan Repke
  8. Algorithmen für reguläre Sprachen basierend auf Algebra (B/M)
    Quelle: [Boj12]
    Vortrag: Sabrina Kielmann
    Betreuung: Martin Lang

  9. Donnerstag, 18.7.2013, 16-18 Uhr

  10. Minimierung von omega-Automaten (B)
    Quellen: [Sch10,Löd01]
    Vortrag: Sven Deserno
    Betreuung: Stefan Repke
  11. Komplementierung von Büchi-Automaten mit Fortschrittsmaßen (B/M)
    Quellen: [Kla91]
    Vortrag: Roman Matzutt
    Betreuung: Christof Löding

Quellen

Die Quellen findet man in der Bibliothek oder zum Teil auch im Internet.

[Boj12] Mikolaj Bojanczyk: Algorithms for regular languages that use algebra. SIGMOD Record 41(2): 5-14 (2012)
[BKW98] Anne Brüggemann-Klein, Derick Wood: One-Unambiguous Regular Languages. Inf. Comput. 140(2): 229-253 (1998)
[DLT01] François Denis, Aurélien Lemay, Alain Terlutte: Residual Finite State Automata. In: STACS 2001, Lecture Notes in Computer Science Volume 2010, 2001, pp. 144-157.
[Kla91] Nils Klarlund: Progress Measures for Complementation of omega-Automata with Applications to Temporal Logic. In: FOCS 1991, pp.358-367
[Löd01] C. Löding. Efficient minimization of deterministic weak omega-automata. Information Processing Letters, 79(3):105-109, 2001.
[LS08] Sylvain Lombardy, Jacques Sakarovitch: The universal automaton In: Jörg Flum, Erich Grädel and Thomas Wilke: Logic and Automata - History and Perspectives, Text in Logic and Games Volume 2, pp. 457-504, Amsterdam University Press, 2008.
[Moh97] Mehryar Mohri. Finite-state transducers in language and speech processing. Comput. Linguist., 23(2):269
[Moh00] Mehryar Mohri: Minimization algorithms for sequential transducers. Theor. Comput. Sci. 234(1-2): 177-201 (2000)
[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.
[SH85] Richard Edwin Stearns, Harry B. Hunt III: On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata. SIAM J. Comput. 14(3): 598-611 (1985)
[VW94] Moshe Y. Vardi, Pierre Wolper: Reasoning About Infinite Computations Inf. Comput. 115(1): 1-37 (1994)