Institute of

Theoretical Computer Science


Technische Universität Braunschweig

Lecture: Algorithmic Automata Theory

Summer term 2018


Mai 28
The lecture of June 4th will be moved to the 15th of June, 11:30 in IZ 349. The new date for the lecture of June 5th will be announced.
March 30
The first lecture will be on Monday, 9th of April at 9:45 in IZ 358.
March 28
Basic information on the course added.


Lecture Notes

The lecture comes with slides (20.11.2013). Moreover, there are handwritten notes, partly from former courses, partly new.
  1. Overview of the topics presented in this course. (Week 1)
  2. Regular languages - Text 1.
  3. Regular languages - Text 2.
  4. Introduction to WMSO. Büchi's theorem - Text 1.
  5. Büchi's theorem - Text 2.
  6. Büchi's theorem - Text 3.
  7. Ehrenfeucht-Fraïssé games - Text 1.
  8. Ehrenfeucht-Fraïssé games - Text 2.
  9. Star-free languages.
  10. Greens Relation and star-free languages.
  11. Presburger arithmetic - Text 1: automata for solution spaces.
  12. Presburger arithmetic - Text 2: quantifier elimination.
  13. Semi-linear sets.
  14. Ginsburg and Spanier's theorem. Parikh's theorem.
  15. Verma, Seidl, Schwentick.
  16. ω-regular Languages. Büchi automata.
  17. Intersection of ω-regular languages. Ramsey's theorem.
  18. Complementation of Büchi automata.
  19. Example on the complementation of Büchi automata.
  20. Decision procedures - Text 1.
  21. Decision procedures - Text 2. LTL - Text 1.


If you have questions or encounter problems with the exercises, please contact Prakash or Peter.



The lectures will be based upon the following books and articles. Most of them are available online, the remaining ones can be found in the library.