Logic and
Theory of
Discrete Systems

Informatik 7

Seminar über Automatentheorie (Sommersemester 2014)

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesung Infinite Computations des WS 2013/14 (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.

Für einen Eindruck möglicher Themen kann man sich die Webseiten zu den früheren Seminaren im Archiv ansehen.

Ablauf und Termine

  • Allgemeine Informationen zum Ablauf findet man auf den Folien aus der Vorbesprechung.
  • Wegen der hohen Teilnehmerzahl wird das Seminar nicht wöchentlich stattfinden, sondern zu einigen Blockterminen gegen Ende der Vorlesungszeit.
  • Folgende Termine sind neben den Vortragsterminen einzuhalten:
    • Erste Absprache mit dem Betreuer bis spätestens 17.4.2014
    • Abgabe der Ausarbeitung: spätestens 3 Wochen vor dem Vortrag

Bei Fragen wenden Sie sich an Christof Löding.

Themen

Donnerstag, 3.7.2014, Seminarraum I7

    • 10 Uhr: Tiling-Systeme (B)
      Quellen: [GR97,LS97]
      Vortrag: Müllers, Till
      Betreuung: Wolfgang Thomas
    • 11 Uhr: 4-Wege-Automaten und Tiling-Systeme (B)
      Quellen: [GR97,BH67,IN77]
      Vortrag: Schmitz, Daniel
      Betreuung: Wolfgang Thomas
    • 14 Uhr: Das Schlangen-Dominoproblem (M)
      Quellen: [Ebb82]
      Vortrag: Müller, Norman
      Betreuung: Wolfgang Thomas
    • 15 Uhr: Kettencode-Sprachen (B)
      Quellen: [MRW82]
      Vortrag: Garus, Amadeus
      Betreuung: Wolfgang Thomas

Freitag 4.7.2014, Raum 5052

    • 10 Uhr: Das Akzeptanzproblem für Büchi-Automaten (M)
      Quellen: [ER66,CT02]
      Vortrag: Schmücking, Jochen
      Betreuung: Benedikt Brütsch
    • 11 Uhr: Omega-Pushdown-Automaten (B)
      Quellen: [CG77]
      Vortrag: Dietrich, Jan-Marcel
      Betreuung: Benedikt Brütsch

Donnerstag 10.7.2014, Seminarraum I7

    • 9 Uhr: Abstände zwischen automatendefinierbaren Sprachen (M)
      Quellen: [CP02]
      Vortrag: Möbus, Sandra
      Betreuung: Martin Lang
    • 10 Uhr: Prime Languages (M)
      Quellen: [KM13]
      Vortrag: Ewald, Tim
      Betreuung: Martin Lang
    • 11 Uhr: Komposition von Automaten für E-Services (M)
      Quellen: [GHIS04]
      Vortrag: Thar, Jan
      Betreuung: Sarah Winter
    • 13 Uhr: Berechnung von Lookahead-Delegatoren für NEAs (M)
      Quellen: [LR13]
      Vortrag: Weber, Elmar
      Betreuung: Sarah Winter
    • 14 Uhr: Quantitative Sprachen (B)
      Quellen: [CDH10]
      Vortrag: Malatenski, Adam
      Betreuung: Christof Löding

Freitag, 11.7.2014, Raum 5052

    • 9 Uhr: Gewichtete Automaten und Online-Algorithmen (M)
      Quellen: [AKL10]
      Vortrag: Martzok, Philip
      Betreuung: Christof Löding
    • 10 Uhr: Übersetzungen in Co-Büchi-Automaten (B)
      Quellen: [BK12]
      Vortrag: Sali, Ömer
      Betreuung: Christof Löding
    • 11 Uhr: Der Erfüllbarkeitstest für LTL (B)
      Quellen: [LZPHV13]
      Vortrag: Recker, Philippe
      Betreuung: Christof Löding
    • 13 Uhr: Omega-Automaten für reelle Funktionen (M)
      Quellen: [CSV13]
      Vortrag: Landwehr, Patrick
      Betreuung: Christof Löding

Quellen

      Die Quellen findet man in der Bibliothek oder zum Teil auch im Internet.
[AKL10] Benjamin Aminof, Orna Kupferman, and Robby Lampert. 2010. Reasoning about online algorithms with weighted automata. ACM Trans. Algorithms 6, 2, Article 28 (April 2010)
[BH67] M. Blum, C. Hewitt.: Automata on a 2-dimensional tape. Proc. 8th IEEE Symp. on Switching and Automata Theory, 155-167, 1967.
[BK12] Udi Boker and Orna Kupferman. 2012. Translating to Co-Büchi Made Tight, Unified, and Useful. ACM Trans. Comput. Logic 13, 4, Article 29 (October 2012)
[CDH10] Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger: Quantitative languages. ACM Trans. Comput. Log. 11(4) (2010)
[CG77] R.S. Cohen, A.Y. Gold, Theory of omega-languages: Characterizations of context-free omega-languages J. Comput. System Sci. 15(2) (1977) 169-184.
[CP02] Christian Choffrut, Giovanni Pighizzini. Distances between languages and reflexivity of relations. Theoretical Computer Science Volume 286, Issue 1, 6 September 2002, Pages 117–138
[CSV13] Swarat Chaudhuri, Sriram Sankaranarayanan, and Moshe Y. Vardi. Regular Real Analysis. LICS, page 509-518. IEEE Computer Society, (2013)
[CT02] O. Carton and W. Thomas. The monadic theory of morphic infinite words and generalizations. Information and Computation, 176:51-76, 2002.
[Ebb82] H.D. Ebbinghaus. Undecidability of some domino connectability problems. Zeitschr. Math. Logik Grundlagen Math., 28 (1982), pp. 331–336
[ER66] C.C. Elgot, M.O. Rabin, Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, J. Symb. Logic 31 (1966), 169-181.
[GHIS04] Çagdaş Evren Gerede, Richard Hull, Oscar H. Ibarra, and Jianwen Su. 2004. Automated composition of e-services: lookaheads. In Proceedings of the 2nd international conference on Service oriented computing (ICSOC '04). ACM, New York, NY, USA, 252-262.
[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.
[IN77] K. Inoue, A. Nakamura. Some properties of two-dimensional on-line tessellation acceptors. Information Sci., 13 (1977), pp. 95–121
[KM13] Orna Kupferman, Jonathan Mosheiff: Prime Languages. MFCS 2013: Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings. Springer 2013 Lecture Notes in Computer Science, pages 607-618.
[LS97] Michel Latteux, David Simplot: Recognizable Picture Languages and Domino Tiling. Theor. Comput. Sci. 178(1-2): 275-283 (1997)
[LR13] Christof Löding and Stefan Repke. Decidability Results on the Existence of Lookahead Delegators for NFA. In Anil Seth and Nisheeth K. Vishnoi, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), volume 24 of Leibniz International Proceedings in Informatics (LIPIcs), pages 327-338, Dagstuhl, Germany, 2013. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[LZPHV13] J. Li, L. Zhang, G. Pu, and J. He, M.Y. Vardi: LTL Satisfiability Checking Revisited. 20th International Symposium on Temporal Representation and Reasoning, TIME'13, to appear.
[MRW82] H.A. Maurer, G. Rozenberg, E. Welzl. Using string languages to describe picture languages. Inform. and Control, 54 (3) (1982), pp. 155–185
[MST02] O. Matz, N. Schweikardt, and W. Thomas: The monadic quantifier alternation hierachy over grids and graphs. Information and Computation, 179:356-383, 2002.
[PP04] D. Perrin and J.-E. Pin. Infinite Words. Pure and Applied Mathematics Vol 141, Elsevier, 2004.
[TL94] W. Thomas and H. Lescow. Logical specifications of infinite computations. In J.W. de Bakker, W.P. de Roever, and G. Rozenberg, editors, REX School/Symposium 1993: A Decade of Concurrency, volume 803 of Lecture Notes in Computer Science, pages 583-621, Noordwijkerhout, The Netherlands, 1994. Springer.