HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01098741
Contributor : Sophie Pinchinat Connect in order to contact the contributor
Submitted on : Monday, December 29, 2014 - 9:48:50 AM
Last modification on : Friday, February 4, 2022 - 3:22:29 AM

Identifiers

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⟩

Share

Metrics

Record views

122