Seminar über Automatentheorie

» Diese Veranstaltung wird auf deutsch gehalten.

Seminar im Wintersemester 2010/2011

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 Vorlesung Angewandte Automatentheorie 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 22.10.2010
    • Abgabe der Ausarbeitung bis zum 21.12.2010 (oder nach Absprache mit Betreuer)
  • Die Vorträge sollten eine Dauer von ca. 50-55 Minuten haben.
  • Die Vorträge finden im Seminarraum am Lehrstuhl 7 statt.

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

Themen

Freitag 21.1.2011

  1. 9-10 Uhr: Max-Plus-Algebra I
    Quelle: [HOW06,Kapitel 1]
    Vortrag: Sebastian Roidl
    Betreuung: M. Zimmermann
  2. 10.15-11.15 Uhr: Max-Plus-Algebra II
    Quelle: [HOW06,Kapitel 2]
    Vortrag: Svenja Schalthöfer
    Betreuung: M. Zimmermann
  3. 11.30-12.30 Uhr: Komplexität des Karp-Miller-Baums
    Quelle: [PW03,Abschnitt 5.2]
    Vortrag: Philipp Schultz
    Betreuung: M. Slaats
  4. 14-15 Uhr: Abwicklungen von Petri-Netzen
    Quelle: [McM95]
    Vortrag: Marlin Frickenschmidt
    Betreuung: M. Slaats
  5. 15:15-16.15 Uhr: Erreichbarkeit in Petri-Netzen
    Quelle: [Ler09]
    Vortrag: Silvio De Carolis
    Betreuung: S. Schulz

Mittwoch 2.2.2011

  1. 10:00-11:00 Uhr: Logische Definierbarkeit von Wortsprachen und -relationen
    Quelle: [Blu99,Kapitel 4]
    Vortrag: Tim Ix
    Betreuung: W. Thomas
  2. 11:15-12:15 Uhr: Die MSO-Hierarchie für Bildsprachen
    Quelle: [MST02]
    Vortrag: Joachim Redies
    Betreuung: F. Radmacher
  3. 14:00-15:00 Uhr: Komplexität der Übersetzung von Logik in Automaten
    Quelle: [Rei02]
    Vortrag: Alexander Kogaj
    Betreuung: W. Thomas
  4. 15:15-16:00 UhrAlgorithmische Theorie unendlicher Graphen
    Quelle: [Tho10]
    Vortrag: Dennis Birkholz
    Betreuung: W. Thomas

Freitag 4.2.2011

  1. 9:00-10:00 Uhr: Rationale Graphen und konstextsensitive Sprachen
    Quelle: [CM06]
    Vortrag: Christiane Heetkamp
    Betreuung: C. Löding
  2. 10.15-11.15 Uhr: Lossy Channel Systems
    Quelle: [AJ96]
    Vortrag: Jonas Dederichs
    Betreuung: F. Radmacher
  3. 11:30-12:30 Uhr: Datenwörter I: Registerautomaten
    Quelle: [Seg06],[KF94]
    Vortrag: Mark Morschhäuser
    Betreuung: C. Löding
  4. 14:00-15:00 Uhr: Datenwörter II: Datenautomaten
    Quelle: [Seg06],[BMSSD06]
    Vortrag: Jan Gossens
    Betreuung: C. Löding
  5. 15:15-16:15 Uhr: Factorization Forests
    Quelle: [Boj09]
    Vortrag: Alexander Richard
    Betreuung: C. Löding

Quellen

[AJ96] Parosh Aziz Abdulla, Bengt Jonsson: Verifying Programs with Unreliable Channels. Inf. Comput. 127(2): 91-101 (1996)
[Blu99] Achim Blumensath, Automatic Structures, Diplomarbeit, RWTH Aachen, 1999.
[BMSSD06] Mikolaj Bojanczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin, Claire David: Two-Variable Logic on Words with Data. 21th IEEE Symposium on Logic in Computer Science (LICS 2006), pp. 7-16, 2006.
[Boj09] Mikolaj Bojanczyk: Factorization Forests. Developments in Language Theory 2009. Lecture Notes in Computer Science 5583, pp. 1-17, Springer, 2009.
[CM06] A. Carayol, A. Meyer: Context-Sensitive Languages, Rational Graphs and Determinism. Logical Methods in Computer Science, vol 2(2), 2006.
[GR97] D. Giammarresi, A. Restivo: Two-dimensional Languages. In Handbook of Formal Languages, G. Rosenberg and A. Salomaa (Eds), Vol. III, Seite 215-268. Springer Verlag, 1997.
[HOW06] B. Heidergott, G.J. Olsder, J van der Woude: Max Plus at Work. Princeton University Press, 2006.
[KF94] Michael Kaminski, Nissim Francez: Finite-Memory Automata. Theor. Comput. Sci. 134(2): 329-363 (1994)
[Ler09] J. Leroux: The General Vector Addition System Reachability Problem by Presburger Inductive Invariants. 24th Annual IEEE Symposium on Logic In Computer Science, LICS 2009.
[McM95] Kenneth L. McMillan: A Technique of State Space Search Based on Unfolding. Formal Methods in System Design 6(1): 45-65 (1995)
[MST02] O. Matz, N. Schweikardt, and W. Thomas: The monadic quantifier alternation hierachy over grids and graphs. Information and Computation, 179:356-383, 2002.
[PW03] L. Priese, H. Wimmel: Petri-Netze. Springer-Verlag, Berlin 2003.
[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.
[Seg06] Luc Segoufin: Automata and Logics for Words and Trees over an Infinite Alphabet. CSL 2006. Lecture Notes in Computer Science 4207, pp. 41-57, Springer 2006.
[Tho10] W. Thomas: Finite Automata and the Analysis of Infinite Transition Systems. In Deepak D'Souza and Priti Shankar, editors, Modern Applications of Automata Theory. World Scientific, 2010. To appear.