Seminar: Automatentheorie (Master/Lehramt)

 

Wintersemester 2015/2016

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 Applied Automata Theory. 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.

 

Organisation

  • Allgemeine Informationen zum Ablauf werden in der Vorbesprechung bekanntgegeben in den [Folien aus der Vorbesprechung].
  • Der Rücktritt von dem Seminar ohne Eintragung eines Fehlversuchs ist bis zu 3 Wochen nach der Vorbesprechung möglich, also bis zum 29.9.2015.
  • Das Seminar findet an drei Blockterminen zum Ende der Vorlesungszeit statt.
  • Die Vorträge sind im Seminarraum am Lehrstuhl 7.
 

Literatur

[AKK14] Shaull Almagor, Denis Kuperberg, Orna Kupferman. Regular Sensing. FSTTCS 2014: 161-173. LIPIcs 29, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
[BC02] Marie-Pierre Béal, Olivier Carton. Determinization of transducers over finite and infinite words. Theoretical Computer Science, Volume 289, Issue 1, 23 October 2002, Pages 225–251
[BGNV08] Geert Jan Bex, Wouter Gelade, Frank Neven, Stijn Vansummeren: Learning deterministic regular expressions for the inference of schemas from XML data. Proceedings of the 17th International Conference on World Wide Web, WWW 2008
[BKW98] Anne Brüggemann-Klein, Derick Wood: One-Unambiguous Regular Languages. Inf. Comput. 140(2): 229-253 (1998)
[EK12] J. Esparza, J. Kreiker: Three Case Studies on Verification of Infinite-State Systems. Kapitel 12 in Modern Applications of Automata Theory. Deepak D'Souza and Priti Shankar (editors), World Scientific, 2012.
[Fer09] H. Fernau:Algorithms for learning regular expressions from positive data. Information and Computation Volume 207, Issue 4, April 2009, Pages 521–541
[FL14] Diego Figueira, Leonid Libkin. Synchronizing Relations on Words. STACS 2014: 518-529. LIPIcs 25, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014
[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
[KV94] M.J. Kearns, U.V. Vazirani An Introduction to Computational Learning Theory. MIT Press, 1994.
[LS08] Sylvain Lombardy, Jacques Sakarovitch: The universal automaton In: Jörg Flum, Erich Grädel and Thomas Wilke: Logic and Automata - History and Perspectives, Text in Logic and Games Volume 2, pp. 457-504, Amsterdam University Press, 2008.
[SH85] Richard Edwin Stearns, Harry B. Hunt III: On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata. SIAM J. Comput. 14(3): 598-611 (1985)