Topic outline

  • General

    Collapse all Expand all
    • Aktualności Forum

    • Exam:

      Part I (written): June 7, 10-12, room 140.

      Part II (oral): June 14, room 140, 10:15-12:15.

  • Lectures

    • Diary

      Week 1: Omega-automata: Buechi, Muller, Rabin and Street acceptance condition, closure under union, intersection and complementation, proof that deterministic Buechi automata are weaker than non-deterministic ones, definition of regular expressions.

      Week 2: Proof that regular expressions, the logic S1S and Buechi automata are equivalent. Complexity of the emptiness and universality problems for Buechi automata.

      Week 3: Games: winning conditions, strategies, memoryless determinancy. Proof that reachability games are determined.

    • Week 4: determinisation of parity games File
      Not available unless: Your Email address is not empty
    • Week 5 - tree automata File
      Not available unless: Your Email address is not empty
    • Week 6 podcast URL
    • Week 7: mean-payoff games File
    • Weeks 8-10: weighted automata File
    • Week 11: probabilistic models File
    • Week 12: synthesis File
    • Week 13: synthesis tools File

    • Recommended reading:

    • 1. Lectures in Game Theory for Computer Scientists, Krzysztof Apt, Erich Gradel File
      Not available unless: Your Email address is not empty
    • 2. Automata, Logics, and Infinite Games: A Guide to Current Research, Erich Gradel, Wolfgang Thomas File
      Not available unless: Your Email address is not empty
    • 3. Logic and Automata: History and Perspectives, Jörg Flum, Erich Grädel, Thomas Wilke et al. File
      Not available unless: Your Email address is not empty
    • 4. Automata, Logic and Games, C.-H. L. Ong File
      Not available unless: Your Email address is not empty
    • 5. The complexity of mean payoff games on graphs, Uri Zwick and Mike Patersonb URL
    • 6. Principles of Model Checking, Christel Baier and Joost-Pieter Katoen Book
      Not available unless: Your Email address is not empty
    • 7. Graph Games and Reactive Synthesis, Roderick Bloem, Krishnendu Chatterjee, and Barbara Jobstmann File
      Not available unless: Your Email address is not empty

  • Exercises