Seminar: Automatentheorie

 

Sommersemester 2014

Kontakt

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

 

Organisation

  • 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

Dozenten

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.