Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Algorithmic Automata Theory 2021

News

April 26
The date for the first tutorial has been added.
March 26
The information on this page is preliminary.

Organization

The course is offered as a self-study course (Selbststudium): there are no lectures (neither in person nor as video). Participants are supposed to work through the below material independently on their own.

There will be online tutorials where participants can ask questions about predefined topics from the lecture notes.

Participants are required to do the exercises listed below. However, the solutions are not marked/graded. Solutions may be discussed during tutorials.

If you have any questions, please contact: Thomas Haas, Sören van der Wall, and Sebastian Wolff.

Tutorials

The tutorials will be given by Thomas Haas, Sören van der Wall, and Sebastian Wolff. Prof. Roland Meyer may join the meetings as well to discuss the material.

Tutorials are optional (not mandatory). Participants are encouraged to prepare questions and send them to the lecturer of the tutorial in advance for smoother operations (in particular, if you have detailed questions on, e.g., some result or proof). We expect to have tutorials every other week. The preliminary schedule for tutorials is as follows:

Lecture Notes

The lecture comes with slides and handwritten notes:
  1. Overview of the topics presented in this course. (Week 1)
  2. Regular languages - Text 1. (Week 1)
  3. Regular languages - Text 2. (Week 1)
  4. Introduction to WMSO. Büchi's theorem - Text 1. (Week 2)
  5. Büchi's theorem - Text 2. (Week 2)
  6. Büchi's theorem - Text 3. (Week 2)
  7. Ehrenfeucht-Fraïssé games - Text 1. (Week 2/3)
  8. Ehrenfeucht-Fraïssé games - Text 2. Star-free languages - Text 1. (Week 3)
  9. Star-free languages - Text 2. (Week 3)
  10. Correction of the finite index proof. (Week 3)
  11. Presburger arithmetic - Text 1: automata for solution spaces. (Week 3/4)
  12. Presburger arithmetic - Text 2: quantifier elimination. (Week 4)
  13. Semi-linear sets. (Week 4/5)
  14. Ginsburg and Spanier's theorem. Parikh's theorem. (Week 5)
  15. Verma, Seidl, Schwentick 2005. (Week 6)
  16. Reversal-bounded Counter Machines. (Week 6/7)
  17. ω-regular Languages. Büchi automata - Text 1. (Week 7)
  18. Intersection of ω-regular languages. König's theorem. Ramsey's theorem. (Week 7)
  19. Complementation of Büchi automata. (Week 8)
  20. Example on the complementation of Büchi automata. (Week 8)
  21. Decision procedures - Text 1. (Week 8)
  22. Decision procedures - Text 2. LTL - Text 1. (Week 9)
  23. LTL - Text 2. (Week 9)
  24. Pushdown systems - Text 1. (Week 9)
  25. Pushdown systems - Text 2. (Week 9/10)
  26. Pushdown systems - Text 3. (Week 10)
  27. Pushdown systems - Examples. (Week 10)
  28. Regular tree languages - Text 1. (Week 10)
  29. Regular tree languages - Text 2. (Week 10)
  30. XML and tree languages - Text 1. (Week 11)
  31. XML and tree languages - Text 2. (Week 11)
  32. Parity games - Text 1. (Week 11)
  33. Parity games - Text 2. (Week 12)
  34. Parity games - Text 3. (Week 12)
  35. Parity tree automata - Text 1. (Week 12)
  36. Parity tree automata - Text 2. (Week 13)
  37. Parity tree automata - Text 3. Rabin's theorem. (Week 13)

Exercises

The exercise sheets are taken from a previous iteration of the lecture (disregard the due date and meta information from the sheets).

Participants have to hand in their solutions to the exercise sheets by the given due date. Send solutions to: Thomas Haas, Sören van der Wall, and Sebastian Wolff.

Content

Literature

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.