Jumping Automata for Uniform Strategies

Bastien Maubert 1 Sophie Pinchinat 1
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : The concept of uniform strategies has recently been proposed as a relevant notion in game theory for computer science. It relies on properties involving sets of plays in two-player turn-based arenas equipped with a binary relation between plays. Among the two notions of fully-uniform and strictly-uniform strategies, we focus on the latter, less explored. We present a language that extends CTL^* with a quantifier over all related plays, which enables to express a rich class of uniformity constraints on strategies. We show that the existence of a uniform strategy is equivalent to the language non-emptiness of a jumping tree automaton. While the existence of a uniform strategy is undecidable for rational binary relations, restricting to ecognizable relations yields a 2EXPTIME-complete complexity, and still captures a class of two-player imperfect-information games with epistemic temporal objectives. This result relies on a translation from jumping tree automata with recognizable relations to two-way tree automata.
Type de document :
Communication dans un congrès
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2013, Guwahati, India. 〈10.4230/LIPIcs.FSTTCS.2013.287〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01098741
Contributeur : Sophie Pinchinat <>
Soumis le : lundi 29 décembre 2014 - 09:48:50
Dernière modification le : mercredi 16 mai 2018 - 11:23:05

Identifiants

Citation

Bastien Maubert, Sophie Pinchinat. Jumping Automata for Uniform Strategies. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2013, Guwahati, India. 〈10.4230/LIPIcs.FSTTCS.2013.287〉. 〈hal-01098741〉

Partager

Métriques

Consultations de la notice

216