Automata and Formal Languages 2008/09

News | Dates | Grading | Content | Exercises | Exam | Material

The lecture will mostly be given on the blackboard. In case we will use slides, they will be put here. Also, we shall provide lecture notes and/or pointers to papers available online.

Programming Competition

• Description

Handouts

• Tobias Nipkow's slides from last term's introductory lecture (in German).
• Deepak D'Souza's handout on monadic second order logic over words and Büchis's theorem about the equivalence of regularity and MSO-definability.
• Madhavan Mukund: Finite-state Automata on Infinite Inputs.
• The material on timed automata.

Results of the Evaluation

Literature

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman;
  Introduction to Automata Theory, Languages and Computation;
  Addison-Wesley Longman, 3rd edition, 2006.
• Joerg Flum, Erich Graedel, Thomas Wilke (eds.);
  Logic and Automata: History and Perspectives, Volume 2;
  Amsterdam University Press, 2008.
• Dominique Perrin, Jean-Eric Pin;
  Infinite Words: Automata, Semigroups, Logic and Games;
  Academic Press, 2004.

Tools

In both exercises and class we will use a number of tools to demonstrate the practical usefulness of the theory and to present typical applications. Here is a list of tools to be used.

• SPIN: to illustrate Büchi automata
• MONA: to illustrate WS1S and corresponding automata
• LTL2BA: translating LTL formulas to Büchi automata
• Uppaal: to play with timed automata