Seminar: Automata Theory (Master)

 

Winter Term 2015/2016

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

 

Organization

  • general information will be given at the initial meeting in the Slides from the introduction.
  • Withdrawal from the seminar without a failed record is possible up to 3 weeks before the presentation, so up to the 29.09.2015.
  • The seminar is held on three block dates at the end of the semester.
  • The presentations will be given in the seminar room at i7.
 

Literature

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

External Links