Seminar über Automatentheorie

» Diese Veranstaltung wird auf deutsch gehalten.

Seminar im Wintersemester 2013/2014

ArtECTSOrtVeranstalter
S2 4 Seminarraum Lehrstuhl Informatik 7 Thomas, Chaturvedi, Felscher

Die Plätze werden im zentralen Vergabeverfahren vergeben.

Allgemeines

In dem Seminar werden Originalarbeiten aus dem Themenumfeld der Vorlesung Angewandte Automatentheorie studiert. Beispiele für Themen findet man auf der Webseite des Seminars aus dem WS12/13.

Vorwissen

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

Ablauf

  • Allgemeine Informationen zum Ablauf werden in der Vorbesprechung bekannt gegeben. Der Termin der Vorbesprechung wird den Teilnehmern per E-Mail mitgeteilt.
  • Laut Prüfungsordnung haben Sie nach der Vorbesprechung 3 Wochen, um sich vom Seminar abzumelden (ohne einen Fehlversuch angerechnet zu bekommen). Danach wird die Anmeldung verbindlich.
  • Das Seminar findet semesterbegleitend in Doppelsitzungen statt, freitags um 10 Uhr.
  • Folgende Termine sind neben den Vortragsterminen einzuhalten:
    • Erste Absprache mit dem Betreuer bis spätestens 9 Wochen vor Vortragstermin
    • Deadline zur Abgabe der Ausarbeitung: bis 3 Wochen vor dem Vortragstermin
  • Die Vorträge sollten eine Dauer von ca. 50-55 Minuten haben.
  • Die Vorträge finden im Seminarraum am Lehrstuhl 7 statt.

Themen

Die Themen sind für Teilnehmer aus dem Studiengang Informatik B.Sc. bzw. M.Sc.

1. Termin: Freitag, 22.11.2013

    Automata on infinite alphabets (B/M)
    Quelle: [Bes08]
    Vortrag: Becker, Julian
    Betreuung: Felscher
    Non-elementary complexity of translation from MSO logic to automata (B)
    Quelle: [Rei02]
    Vortrag: Behrendt, Matthias
    Betreuung: Felscher

2. Termin: Freitag, 29.11.2013

    Model-checking synchronized products (M)
    Quelle: [WT04]
    Vortrag: Schumacher, Andreas
    Betreuung: Felscher
    Non-elementary complexity of model composition (M)
    Quelle: [DGKS07]
    Vortrag: Nicolas, Osterloh
    Betreuung: Felscher

3. Termin: Freitag, 06.12.2013 (9:30h)

    Green's relations (B)
    Quelle: [Col11] [Pin86]
    Vortrag: Spinrath, Christopher
    Betreuung: Chaturvedi

4. Termin: Freitag, 13.12.2013 (9:30h)

    Schuetzenberger's Theorem (M)
    Quelle: [Col11]
    Vortrag: Gödicke, Maximilian
    Betreuung: Chaturvedi
    Visibly pushdown automata (B)
    Quelle: [AM04]
    Vortrag: Buss, Hilke
    Betreuung: Chaturvedi
    Logics for visibly pushdown automata; MSO + CARET (M)
    Quelle: [AM04] (Section 3), [AEM04]
    Vortrag: Biebricher, Julius
    Betreuung: Chaturvedi
    Vier-Wege-Automaten und TC-Logik (B)
    Quelle: [BM91], [Pot94]
    Vortrag: Reinker, Niklas
    Betreuung: Thomas

5. Termin: Freitag, 17.01.2014 (9:30h)

    Prefix recognizable graphs: complexity of reachability (B)
    Quelle: [Göl08]
    Vortrag: Tran, Duc Thanh
    Betreuung: Thomas
    Pushdown graphs and Muller Schupp Theorem (M)
    Quelle: [MS85]
    Vortrag: Neuen, Daniel
    Betreuung: Thomas
    Rational graphs and undecidability results (B)
    Quelle: [Tho02]
    Vortrag: Stahlmann, Stephan
    Betreuung: Thomas

6. Termin: Freitag, 24.01.2014 (9:30h)

    Rational graphs and context-sensitive languages (B/M)
    Quelle: [CM06]
    Vortrag: Tang, Mietze
    Betreuung: Thomas
    Kontextsensitive Sprachen: Der Satz von Immerman und Szelepcsenyi (B)
    Quelle: [Gur]
    Vortrag: Lipp, Kai
    Betreuung: Thomas
    Minimierung von Buechi-Automaten (M)
    Quelle: [EWS05]
    Vortrag: Jourenko, Maxim
    Betreuung: Thomas

7. Termin: Freitag, 31.01.2014 (10:00h)

    Reachability over vector addition systems (Petri nets), part 1 (M)
    Quelle: [Ler12]
    Vortrag: Marx, Thorsten
    Betreuung: Thomas
    Reachability over vector addition systems (Petri nets), part 2 (M)
    Quelle: [Ler12]
    Vortrag: Czyba, Christopher
    Betreuung: Thomas

Quellen

Die Quellen findet man im Internet oder in der Bibliothek. Beschaffung der Literatur ist Teil des Seminars.

[AEM04] Rajeev Alur, Kousha Etessami, P. Madhusudan: A Temporal Logic of Nested Calls and Returns In: 10. TACAS 2004: Barcelona, Spain (Part of ETAPS 2004), pages 467-481, 2004
[AM04] Rajeev Alur, P. Madhusudan: Visibly pushdown languages In: 36. STOC 2004: Chicago, pages 202-211, IL, USA, 2004
[Bes08] Alexis Bès: An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet In: Logical Methods in Computer Science 4(1), 2008
[BM91] Y. Bargury, J.A. Makowsky: The Expressive Power of Transitive Closue and 2-way Multihead Automata. CSL 1991: 1-14.
[CM06] Arnaud Carayol, Antoine Meyer: Context-Sensitive Languages, Rational Graphs and Determinism. In: Logical Methods in Computer Science 2(2), 2006
[Col11] Thomas Colcombet: Green's Relations and Their Use in Automata Theory In: Language and Automata Theory and Applications - 5th International Conference, pages 1-21 LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings. Springer 2011
[DGKS07] Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt: Model theory makes formulas large In: ICALP'07: 34th Int. Colloquium on Automata, Languages and Programming, volume 4596 of Lecture Notes in Computer Science, pages 913-924. Springer, 2007.
[EWS05] K. Etessami, Th. Wilke, R.A. Schuller: Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata. SIAM J. Comput. 34(5): 1159-1175 (2005)
[Göl08] Stefan Göller: Reachability on prefix-recognizable graphs In: Information Processing Letters, Volume 108(2), pages 71-74, 2008
[Gur] E. Gurari, An Introduction to the Theory of Computation, Sect 5.5
[Ler12] Jerome Leroux. Vector Addition Systems Reachability Problem (A Simpler Solution). In Andrei Voronkov, editor, The Alan Turing Centenary Conference, Turing-100, Manchester UK June 22-25, 2012, Proceedings, volume 10 of EPiC Series, pages 214-228, 2012
[MS85] David E. Muller, Paul E. Schupp: The Theory of Ends, Pushdown Automata, and Second-Order Logic. In: Theoretical Computer Science, Volume 37, pages 51-75, 1985
[Pin86] J.E. Pin: Varieties for Formal Languages. Plenum Press, New York 1986., Chapter 3 Sections 1-2
[Pot94] A. Potthoff. Logische Klassifizierung regulärer Baumsprachen, Dissertation, Christian-Albrechts-Universität Kiel, 1994, Kap. 3
[Rei02] Klaus Reinhardt: The Complexity of Translating Logic To Finite Automata In: Erich Grädel, Wolfgang Thomas and Thomas Wilke: Automata, Logics, and Infinite Games - A Guide to Current Research Lecture Notes in Computer Science 2500, pp. 231-238, 2002.
[Tho02] W. Thomas. A short introduction to infinite automata. In Proceedings of the 5th international conference Developments in Language Theory, volume 2295 of Lecture Notes in Computer Science, pages 130-144. Springer, 2002. (c) Springer
[WT04] Stefan Wöhrle, Wolfgang Thomas: Model Checking Synchronized Products of Infinite Transition Systems In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, LNCS, pages 2-11, Washington, DC, USA, 2004. IEEE Computer Society.