Seminar: Automata Theory

 

Summer Term 2015

Contact

Name

Christof Löding

Phone

work
+49 241 80 21712

Email

E-Mail
 
 

Content

Subject of this seminar are original works and overview articles concerning automata theory, usually with emphasis in the vicinity of the lecture Infinite Computations, the topics will be depending on the knowlege of the participants and eventually adapted to accommodate topics of Applied Automata Theory. Active participation of this lecture or similar lectures in previous terms including the exercises are helpful in handling the topics and will be considered when apointing the slots.

It is a seminar of theoretical computer science. It will be required that the students know how to handle abstract models and mathematical proof.

For an idea of possible topics some web sites of previous terms can be found on the Archiv.

 

Organization

  • General information concerning the procedure will be covered during the introduction.
  • Presentations: 3 block dates in July; at the moment planed (afternoons):
    • Thursday 2.7.2015
    • Wednesday 8.7.2015
    • Thursday 9.7.2015
  • the folling dates are to be kept in addition to the presentation dates:
    • First consultation with your sponsor till 24.4.2015
    • Delivery of the draft: latest three weeks prevous to your presentation
 

Literature

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

External Links