Institute of

Theoretical Computer Science


Technische Universität Braunschweig

Concurrency Theory 2015



Dates and rooms:


There will be oral exams in 34-418 on the following dates: To be admitted, you have to fulfil the following requirements:
  1. 60 percent of your exercises have to be marked by a plus.
  2. You have to present some of your exercise solutions on the board .

Lecture Notes

The parts on Petri nets and well-structured transition systems will be based on these lecture notes.

Moreover, there are handwritten notes on the other topics of the lecture:

  1. Rackoff's Upper Bound 1. (Week 1)
  2. Rackoff's Upper Bound 2 (full). (Week 2)
  3. Lipton's Lower Bound 1. (Week 3)
  4. Lipton's Lower Bound 2. (Week 3)
  5. Excursion on Invariants and Reachability in Petri nets. (Week 4)
  6. Traps and Verification Systems. See lecture notes. (Week 5)
  7. Well-Quasi-Orderings, Well-Structured Transition Systems, Lossy Channel Systems. See lecture notes. (Week 6)
  8. Downward Closures and Antichains. (Week 7)
  9. Treewidth. (Week 7, 8)
  10. MSO and MSO Interpretations. (Week 8)
  11. Courcelle's Theorem. (Week 9)
  12. Additional material on Büchi's theorem: MSO on words, Büchi I (from NFA to MSO), started with Büchi II (from MSO to NFA), Büchi II. Büchi II is the construction needed for Courcelle's theorem. (Week 9)
  13. Formal languages. (Weeks 10 through 14)



Exercise Sheets:

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