Speaker: Martin Zimmermann, Universität des Saarlandes

Title: The Complexity of Counting Models of Linear-time Temporal Logic

Abstract:

We determine the complexity of counting models of bounded size of specifications expressed in Linear-time Temporal Logic. Counting word models is #P-complete, if the bound is given in unary, and as hard as counting accepting runs of non-deterministic polynomial-space Turing machines, if the bound is given in binary. Counting tree models is as hard as counting accepting runs of non-deterministic exponential-time Turing machines, if the bound is given in unary. For a binary encoding of the bound, the problem is at least as hard as counting accepting runs of non-deterministic exponential space Turing machines. On the other hand, it is not harder than counting accepting runs of non-deterministic doubly-exponential time Turing machines.

This is joint work with Hazem Torfah.

http://arxiv.org/abs/1408.5752

Speaker: Felix Klein, Universität des Saarlandes

Title: How Much Lookahead is Needed to Win Infinite Games?

Abstract:

Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent’s moves. For omega-regular winning conditions it is known that such games can be solved in doubly-exponential time and that doubly-exponential lookahead is sufficient.

We improve upon both results by giving an exponential time algorithm and an exponential upper bound on the necessary lookahead. This is complemented by showing EXPTIME-hardness of the solution problem and tight exponential lower bounds on the lookahead. Both lower bounds already hold for safety conditions. Furthermore, solving delay games with reachability conditions is shown to be PSPACE-complete.

This is joint work with Martin Zimmermann.