Seminar über Automatentheorie

» This course is given in German.

Seminar im Wintersemester 2009/2010

ArtECTSOrtVeranstalter
S2 4 Seminarraum Lehrstuhl Informatik 7 Thomas, Löding

Die Plätze werden im zentralen Vergabeverfahren vergeben.

Allgemeines

In dem Seminar werden Originalarbeiten aus dem Themenumfeld der Vorlesungen Angewandte Automatentheorie und Baumautomaten studiert.

Vorwissen

Gute Vorkenntnisse der Automatentheorie, vorzugsweise belegt durch erfolgreiche Teilnahme an Übungen zu Vorlesungen des Lehrstuhls, sind erwünscht.

Ablauf

  • Allgemeine Informationen zum Ablauf findet man auf den Folien aus der Vorbesprechung
  • Folgende Termine sind neben den Vortragsterminen einzuhalten:
    • Erste Absprache mit dem Betreuer bis spätestens 23.10.2009
    • Abgabe der Ausarbeitung bis zum 11.12.2009

Termine

Das Seminar findet in 3 Blöcken an folgenden Tagen statt (nach der aktuellen Terminplanung):

  • Freitag 15.1.10
  • Freitag 5.2.10
  • Montag 8.2.10
Die Zeiten für die einzelnen Vorträge sind unten aufgeführt.

Die Vorträge finden im Seminarraum am Lehrstuhl 7 statt.

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

Vorträge am 15.1.10

  1. 9 Uhr
    Universalautomat I - Definition und Eigenschaften
    Quelle: [LS07]
    Vortrag: Michael Brysch
    Betreuung: C. Löding
  2. 10:15 Uhr
    Universalautomat II - Konstruktion und NEA-Minimierung
    Quelle: [LS07]
    Vortrag: David Rasmus Piegdon
    Betreuung: C. Löding
  3. 11:30 Uhr
    Äquivalenztest für eindeutige NEAs
    Quelle: [SH85]
    Vortrag: Sebastian Bergmann
    Betreuung: M. Holtmann
  4. 14 Uhr
    Komplexität der Übersetzung von Logik in Automaten
    Quelle: [Rei02]
    Vortrag: Annette Huhn
    Betreuung: W. Thomas
  5. -
    Ein vollständiges Umformungssystem für reguläre Ausdrücke
    Quelle: [Koz94]
    Vortrag: entällt
    Betreuung: F. Radmacher

Vorträge am 5.2.10

  1. 9 Uhr
    Eine logische Charakterisierung der kontextfreien Sprachen
    Quelle: [LST94]
    Vortrag: Yannic Maus
    Betreuung: M. Zimmermann
  2. 10:15 Uhr
    Deterministische Top-Down-Baumautomaten
    Quelle: [GS84]
    Vortrag: Patrick Zimmer
    Betreuung: A. Spelten
  3. 11:30 Uhr
    Deterministische reguläre Ausdrücke
    Quelle: [BKW98]
    Vortrag: Stefan Breuers
    Betreuung: K. Wong
  4. 14 Uhr
    Lernverfahren für deterministische reguläre Ausdrücke
    Quelle: [BGNV08]
    Vortrag: Matthias Rüdiger
    Betreuung: K. Wong
  5. 15:15 Uhr
    Durchschnitt und Komplement für reguläre Ausdrücke
    Quelle: [GN08]
    Vortrag: Michael Kramp
    Betreuung: M. Holtmann

Vorträge am 8.2.10

  1. 9 Uhr
    Hierarchische Automaten
    Quelle: [AY01]
    Vortrag: Thomas Heinemann
    Betreuung: J. Olschewski
  2. 10:15 Uhr
    Nebenläufigkeit und Alternation in Automaten
    Quelle: [DH94]
    Vortrag: Sten Gruener
    Betreuung: J. Olschewski
  3. 11:30 Uhr
    Abwicklungen von Petri-Netzen: Beschränkte Netze und Deadlocks
    Quelle: [McM95]
    Vortrag: Noradej Peamwaiprib
    Betreuung: F. Radmacher
  4. 14 Uhr
    Abwicklungen von Petri-Netzen: Unbeschränkte Netze und Überdeckungen
    Quelle: [AIN00]
    Vortrag: Gökay Bodur
    Betreuung: F. Radmacher
  5. 15:15 Uhr
    Synchronisation in Automaten
    Quelle: [Vol08]
    Vortrag: Marian Van de veire
    Betreuung: J. Olschewski

Quellen

[AIN00] Parosh Aziz Abdulla, S. Purushothaman Iyer, Aletta Nylén: Unfoldings of Unbounded Petri Nets. Computer Aided Verification, 12th International Conference, CAV 2000, Chicago, IL, USA, July 15-19, 2000, Proceedings. Lecture Notes in Computer Science 1855 Springer 2000
[AY01] Rajeev Alur, Mihalis Yannakakis: Model checking of hierarchical state machines. ACM Trans. Program. Lang. Syst. 23(3): 273-303 (2001)
[BGNV08] Geert Jan Bex, Wouter Gelade, Frank Neven, Stijn Vansummeren: Learning deterministic regular expressions for the inference of schemas from XML data. Proceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, 2008. ACM 2008
[BW98] Anne Brüggemann-Klein, Derick Wood: One-Unambiguous Regular Languages. Inf. Comput. 140(2): 229-253 (1998)
[DH94] Doron Drusinsky, David Harel: On the Power of Bounded Concurrency I: Finite Automata. J. ACM 41(3): 517-539 (1994)
[GS84] F. Gesec, M. Steinby. Tree Automata. (Akademial Kiado, Budapest, 1984)
[GN08] Wouter Gelade, Frank Neven: Succinctness of the Complement and Intersection of Regular Expressions. STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings. Dagstuhl Seminar Proceedings 08001 Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008
[Koz94] Dexter Kozen: A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events Inf. Comput. 110(2): 366-390 (1994)
[LS07] Sylvain Lombardy, Jacques Sakarovitch: The universal automaton. Logic and automata: History and Perspectives, Amsterdam University Press, pages 457--504, 2007
[LST94] Clemens Lautemann, Thomas Schwentick, Denis Thérien: Logics For Context-Free Languages. Computer Science Logic, 8th International Workshop, CSL '94, Kazimierz, Poland, September 25-30, 1994, Selected Papers. Lecture Notes in Computer Science 933 Springer 1995
[McM95] Kenneth L. McMillan: A Technique of State Space Search Based on Unfolding. Formal Methods in System Design 6(1): 45-65 (1995)
[Rei02] Klaus Reinhardt: The Complexity of Translating Logic to Finite Automata. Automata, Logics, and Infinite Games: A Guide to Current Research Lecture Notes in Computer Science 2500 Springer 2002,
[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)
[Vol08] Mikhail V. Volkov: Synchronizing Automata and the Cerny Conjecture. Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers. Lecture Notes in Computer Science 5196 Springer 2008.