Automata and Formal Languages 2009/10

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

This lecture requires basic knowledge in automata theory, e.g., obtained during the course 'Einführung in die theoretische Informatik'. Below there is a rough outline of the topics. This list is subject to change and will be updated based on progress and student input.

1. Finite Automata over finite words
   1. Classical constructions for DFA (union, intersection, complement, determinization)
   2. Algorithms and complexity of such constructions (e.g. PSPACE-completeness of universality of DFA)
   3. Applications: pattern matching, verification
2. Finite Automata over infinite words
   1. Omega words and omega automata
   2. Büchi automata
   3. Union, Product, Determinization, Complement
   4. Muller, Rabin, Street automata
   5. Büchi automata in verification
3. Automata and Logic
   1. Monadic Second Order Logic (MSO) over words
   2. Equivalence of MSO and regular languages
   3. Monadic Second Order logic of One successor (S1S)
   4. Equivalence of MSO and omega-regular languages
   5. Presburger arithmetic
   6. Linear Temporal Logic (LTL)
4. Timed Automata