Informatik an der TU Clausthal > Abteilungen > Computational Intelligence > Computational Intelligence > Teaching > International Lecturing > Decision Problems and Decision Procedures for Strategic Logics (ESSLLI 2011)

Decision Problems and Decision Procedures for Strategic Logics (ESSLLI 2011)

 

Lecturers

Dr. Nils Bulling (TU Clausthal)

Dr. Wojtek Jamroga (University of Luxembourg)

 

Misc

  • Time: 1. August - 5. August 2011, 11:00 -12:30

 

Schedule

  • Lecture 1: Modal logics of games and strategies. 
    • Modal Logic; reasoning about time: temporal logic
    • Reasoning about strategies: coalition logic, alternating-time temporal logic; semantic variants of ATL, abilities under imperfect information
  • Lecture 2: Validity in strategic logics.
    • Axiomatizations of CL and ATL. Comparing validities between semantic variants of ATL
    • Satisfiability in temporal and strategic logics: main complexity results.
  • Lecture 3: Model checking of time and abilities I
    • Model checking CTL, LTL and CTL*: basic algorithms, complexity results for explicit models. Model complexity vs. formula complexity.
    • Model Checking ATL
  • Lecture 4: Model checking of time and abilities II
    • Model checking ATL: complexity results for explicit models. Model complexity vs. formula complexity. Other syntactic variants: ATL+, ATL*.
  • Lecture 5: Imperfect information and complexity of "practical" model checking.
    • Model checking agents with imperfect information. Complexity results and proof sketches. Undecidability of imperfect information/perfect recall. Looking for polynomial verification: AEMC.
    • Verification complexity for finer-grained measures of input. State-space explosion. Complexity for compact representations. Symbolic model checking: models, algorithms, tools.

Prerequisites

The course requires some basic knowledge on automata theory, complexity theory (Turing machines, reductions, P, NP, PSPACE, etc.) and some elementary understanding of propositional logic.

Slides and Course Reader

Coming soon...

 

Material

esslli2011WJ.pdf

Preliminary slides Day 1 and 3 (Wojtek)

esslli-2011.pdf

Slides Day 2,3, and 4 (Nils), preliminary, 4.8.2011

 

Kontakt  Suche  Sitemap  Datenschutz  Imprint
© TU Clausthal 2017