Logic and
Theory of
Discrete Systems

Informatik 7

Seminar über Automatentheorie (Sommersemester 2015)

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesungen Infinite Computations sowie Angewandte Automatentheorie. Aktive Teilnahme an einer dieser Vorlesungen (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 werden in der Vorbesprechung bekanntgegeben.
  • Vortragstermine: 3 Blocktermine im Juli; derzeit sind geplant (jeweils nachmittags):
    • Donnerstag 2.7.2015
    • Mittwoch 8.7.2015
    • Donnerstag 9.7.2015
  • Folgende Termine sind neben den Vortragsterminen einzuhalten:
    • Erste Absprache mit dem Betreuer bis 24.4.2015
    • Abgabe der Ausarbeitung: spätestens 3 Wochen vor dem Vortrag

Bei Fragen wenden Sie sich an Christof Löding.

Themen und Termine

Die Vorträge finden im Seminarraum am Lehrstuhl Informatik 7 statt (Raum 4116)

Donnerstag, 2. Juli 2015

  • 13 Uhr: Unentscheidbare Erweiterung von MSO über (N,+1) (Quelle: [ER66], [Tho78]; Betreuung: Wolfgang Thomas; Vortrag: Leandro Eichenberger)
  • 14 Uhr: Omega-Sprachen jenseits der regulären Omega-Sprachen (Quelle: [TL94]; Betreuung: Wolfgang Thomas; Vortrag: Simon Siewert)

Mittwoch, 8. Juli 2015

  • 13 Uhr: Entscheidbare Erweiterung von MSO über (N,+1) (Quelle: [ER66]; Betreuung: Wolfgang Thomas; Vortrag: Etibar Sadigov)
  • 14 Uhr: Omega-Automaten für reelle Funktionen (Quelle: [CSV13]; Betreuung: Christof Löding; Vortrag: Karsten Ansteeg)
  • 15 Uhr: Network-Formation Games with Regular Objectives (Quelle: [AKT14]; Betreuung: Benedikt Brütsch; Vortrag: Alexander aus der Fünten)

Donnerstag, 9. Juli 2015

  • 13 Uhr: Regular Sensing (Quelle: [AKK14]; Betreuung: Benedikt Brütsch; Vortrag: David Schmalzing)
  • 14 Uhr: Properties and Utilization of Capacitated Automata (Quelle: [KT14]; Betreuung: Christof Löding; Vortrag: Sandra-Jasmin Petrut)
  • 15 Uhr: Synchronisierende Automaten (Quelle:[Vol08]; Betreuung: Christof Löding; Vortrag: Frank Weidler)

 

Quellen

Die Quellen findet man in der Bibliothek oder zum Teil auch im Internet.

[AKK14]  Shaull Almagor, Denis Kuperberg, Orna Kupferman. Regular Sensing. FSTTCS 2014: 161-173. LIPIcs 29, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
[AKT14] Guy Avni, Orna Kupferman, Tami Tamir. Network-Formation Games with Regular Objectives. FoSSaCS 2014: 119-133. Lecture Notes in Computer Science 8412, Springer 2014
[Bar15] Stephan Barth. Deciding Monadic Second Order Logic over omega-words by Specialized Finite Automata. submitted, 2015
[CNP94] Hugues Calbrix, Maurice Nivat, Andreas Podelski: Ultimately Periodic Words of Rational w-Languages. MFPS 1993. Lecture Notes in Computer Science 802, pp. 554-566, Springer 1994
[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)
[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.
 [FL14] Diego Figueira, Leonid Libkin. Synchronizing Relations on Words. STACS 2014: 518-529. LIPIcs 25, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
[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.
[KT14] Orna Kupferman, Tami Tamir. Properties and Utilization of Capacitated Automata (Invited Talk). FSTTCS 2014: 33-44. LIPIcs 29, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
 [Tho78] Wolfgang Thomas. The theory of successor with an extra predicate. Mathematische Annalen 1978, Volume 237, Issue 2, pp 121-132
[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.
[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.
FaLang translation system by Faboba