Seminar: Automata Theory

 

Summer Term 2014

 

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 participant altered to accommodate Angewandte Automatentheorie). 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 in the Archiv.

 

Organization

• General information can be found at slides of the introduction (german only).
• As a result of the large attendance this seminar won't be held weekly but on a few dates as a block course at the end of the semester.
• The following dates have to be remembered appart from the date of presentation:
• The first talk with your supervisor before the 17.4.2014
• due date: a maximum of three weeks before the presentation

Instructors

Wolfgang Thomas
Christof Löding

 

Literatur

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