Speaker: Erman Acar (VU Amsterdam)
Date and Time: Thursday, September 19th 2019, 16:30-18:00
Venue: ILLC Seminar Room F1.15, Science Park 107.
Title: When Satisfiability is easier than Model Checking: A Fragment of Strategy Logic.
Abstract. In the design of complex systems, model-checking and satisfiability arise as two prominent decision problems. While model-checking requires the designed system to be provided in advance, satisfiability allows to check if such a system even exists. With very few exceptions, the second problem turns out to be harder than the first one from a complexity-theoretic point of view. In this talk, I will present a recent work which investigates the connection between the two problems for a non-trivial fragment of Strategy Logic (SL) which extends Linear Temporal Logic with first-order quantifications over strategies, thus allowing to explicitly reason about the strategic abilities of agents in a multi-agent system. The SL fragment we consider is obtained by preventing strategic quantifications within the scope of temporal operators. The resulting logic is quite powerful, still allowing to express important game-theoretic properties of multi-agent systems, such as existence of Nash and immune equilibria, as well as to formalise the rational synthesis problem. It turns out that satisfiability for such a fragment is PSPACE-COMPLETE, while its model-checking complexity is 2EXPTIME-HARD. The result is obtained by means of an elegant encoding of the problem into the satisfiability of conjunctive-binding first-order logic, a recently discovered decidable fragment of first-order logic. This is a joint work with Massimo Benerecetti and Fabio Mogavero.