12:00-1:00 pm, Lecture Hall 3
Parameterized Complexity of CTL: A Generalization of Courcelle's Theorem
Arne Meier
Leibniz University, Hannover, Germany.
24-11-14

---

Abstract

We present an almost complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. The classification shows a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The only real operator fragments which is in FPT is the fragment containing solely AX. Also we prove a generalization of Courcelle's theorem to infinite signatures which will be used to proof the FPT-membership cases.