The Complexity of Synthesizing Uniform Strategies

Bastien Maubert 1 Sophie Pinchinat 1 Laura Bozzelli 2
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We investigate uniformity properties of strategies. These properties involve sets of plays in order to express useful constraints on strategies that are not \mu-calculus definable. Typically, we can state that a strategy is observation-based. We propose a formal language to specify uniformity properties, interpreted over two-player turn-based arenas equipped with a binary relation between plays. This way, we capture e.g. games with winning conditions expressible in epistemic temporal logic, whose underlying equivalence relation between plays reflects the observational capabilities of agents (for example, synchronous perfect recall). Our framework naturally generalizes many other situations from the literature. We establish that the problem of synthesizing strategies under uniformity constraints based on regular binary relations between plays is non-elementary complete.
Type de document :
Communication dans un congrès
Fabio Mogavero and Aniello Murano and Moshe Y. Vardi. 1st International Workshop on Strategic Reasoning, 2013, Mar 2013, Rome, Italy. EPTCS, 112, pp.8, 2013, EPTCS. 〈10.4204/EPTCS.112.17〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01098745
Contributeur : Sophie Pinchinat <>
Soumis le : lundi 29 décembre 2014 - 10:12:11
Dernière modification le : jeudi 11 janvier 2018 - 06:20:10

Identifiants

Collections

Citation

Bastien Maubert, Sophie Pinchinat, Laura Bozzelli. The Complexity of Synthesizing Uniform Strategies. Fabio Mogavero and Aniello Murano and Moshe Y. Vardi. 1st International Workshop on Strategic Reasoning, 2013, Mar 2013, Rome, Italy. EPTCS, 112, pp.8, 2013, EPTCS. 〈10.4204/EPTCS.112.17〉. 〈hal-01098745〉

Partager

Métriques

Consultations de la notice

236