Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Advanced Automata Theory 2016

News

Organisation

Lecture Notes

The lecture comes with slides (20.11.2013). Moreover, there are handwritten notes, partly from last year, partly new.
  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 3)
  8. Ehrenfeucht-Fraïssé games - Text 2. (Week 3)
  9. Star-free languages (Week 3/4)
  10. Presburger arithmetic - Text 1: automata for solution spaces. (Week 4)
  11. Presburger arithmetic - Text 2: quantifier elimination. (Week 4/5)
  12. Semi-linear sets. (Week 5)
  13. Ginsburg and Spanier's theorem. Parikh's theorem. (Week 5)
  14. Reversal-bounded Counter Machines. (Week 6)
  15. ω-regular Languages. Büchi automata - Text 1. (Week 6)
  16. Intersection of ω-regular languages. Ramsey's theorem. (Week 7)
  17. Complementation of Büchi automata. (Week 7)
  18. Example on the complementation of Büchi automata. (Week 7)
  19. Decision procedures - Text 1. (Week 8)
  20. Decision procedures - Text 2. LTL - Text 1. (Week 8)
  21. LTL - Text 2. (Week 9)
  22. Pushdown systems - Text 1. (Week 9)
  23. Pushdown systems - Text 2. (Week 10)
  24. Pushdown systems - Text 3. (Week 10)
  25. Pushdown systems - Examples. (Week 10)
  26. Regular tree languages - Text 1. (Week 11)
  27. Regular tree languages - Text 2. (Week 11)
  28. Parity games - Text 1. (Week 12)
  29. Parity games - Text 2. (Week 12)
  30. Parity games - Text 3. (Week 12)
  31. Parity tree automata - Text 1. (Week 13)
  32. Parity tree automata - Text 2. (Week 13)
  33. Parity tree automata - Text 3. Rabin's theorem. (Week 13)
  34. A sneak peek at our research:
    First-Order with reachability for infinite-state systems (for the paper see below)
  35. My big fat last recap
Additional resources

Exercises

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

Contents

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.