Seminar über Automatentheorie

» Diese Veranstaltung wird auf deutsch gehalten.

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

Themen

  1. Universalautomat I - Definition und Eigenschaften
    Quelle: [LS07]
    Vortrag: Michael Brysch
    Betreuung: C. Löding
  2. Universalautomat II - Konstruktion und NEA-Minimierung
    Quelle: [LS07]
    Vortrag: David Rasmus Piegdon
    Betreuung: C. Löding
  3. Äquivalenztest für eindeutige NEAs
    Quelle: [SH85]
    Vortrag: Sebastian Bergmann
    Betreuung: M. Holtmann
  4. Komplexität der Übersetzung von Logik in Automaten
    Quelle: [Rei02]
    Vortrag: Annette Huhn
    Betreuung: W. Thomas
  5. Eine logische Charakterisierung der kontextfreien Sprachen
    Quelle: [LST94]
    Vortrag: Yannic Maus
    Betreuung: M. Zimmermann
  6. Ein vollständiges Umformungssystem für reguläre Ausdrücke
    Quelle: [Koz94]
    Vortrag: Malte Schirmacher
    Betreuung: F. Radmacher
  7. Durchschnitt und Komplement für reguläre Ausdrücke
    Quelle: [GN08]
    Vortrag: Michael Kramp
    Betreuung: M. Holtmann
  8. Deterministische reguläre Ausdrücke
    Quelle: [BKW98]
    Vortrag: Stefan Breuers
    Betreuung: K. Wong
  9. Lernverfahren für deterministische reguläre Ausdrücke
    Quelle: [BGNV08]
    Vortrag: Matthias Rüdiger
    Betreuung: K. Wong
  10. Deterministische Top-Down-Baumautomaten
    Quelle: [GS84]
    Vortrag: Patrick Zimmer
    Betreuung: A. Spelten
  11. Hierarchische Automaten
    Quelle: [AY01]
    Vortrag: Thomas Heinemann
    Betreuung: J. Olschewski
  12. Nebenläufigkeit und Alternation in Automaten
    Quelle: [DH94]
    Vortrag: Sten Gruener
    Betreuung: J. Olschewski
  13. Synchronisation in Automaten
    Quelle: [Vol08]
    Vortrag: Marian Van de veire
    Betreuung: J. Olschewski
  14. Abwicklungen von Petri-Netzen: Beschränkte Netze und Deadlocks
    Quelle: [McM95]
    Vortrag: Noradej Peamwaiprib
    Betreuung: F. Radmacher
  15. Abwicklungen von Petri-Netzen: Unbeschränkte Netze und Überdeckungen
    Quelle: [AIN00]
    Vortrag: Gökay Bodur
    Betreuung: F. Radmacher

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
[BKW98] 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.