Seminar: Automatentheorie

 

Sommersemester 2015

Kontakt

Name

Christof Löding

Telefon

work
+49 241 80 21712

E-Mail

E-Mail
 
 

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Automatentheorie, voraussichtlich mit einem Schwerpunkt im Umkreis der Vorlesung Infinite Computations, dabei werden die Themen 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.

 

Organisation

  • 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
 

Literatur

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

Externe Links