Authors: Raphaël Berthon, Bastien Maubert, Aniello Murano, Sasha Rubin and Moshe Vardi
Paper Information
Title: | Strategy Logic with Imperfect Information |
Authors: | Raphaël Berthon, Bastien Maubert, Aniello Murano, Sasha Rubin and Moshe Vardi |
Proceedings: | SR SR18 papers |
Editors: | Nicolas Markey and Patricia Bouyer |
Keywords: | Strategy Logic, Model checking, Imperfect information, Hierarchical information |
Abstract: | ABSTRACT. We introduce an extension of Strategy logic for the imperfect-information setting, called SLii, and study its model-checking problem. As this logic naturally captures multi-player games with imperfect information, the problem turns out to be undecidable. We introduce a syntactical class of "hierarchical instances" for which, intuitively, as one goes down the syntactic tree of the formula, strategy quantifications are concerned with finer observations of the model. We prove that model-checking SLii restricted to hierarchical instances is decidable. This result, because it allows for complex patterns of existential and universal quantification on strategies, greatly generalises previous ones, such as decidability of multi-player games with imperfect information and hierarchical observations, and decidability of distributed synthesis for hierarchical systems. |
Pages: | 15 |
Talk: | Jul 08 16:40 (Session 42Q: Strategy Logic) |
Paper: |