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
Contributor : Sophie Pinchinat <>
Submitted on : Monday, December 29, 2014 - 9:48:50 AM
Last modification on : Thursday, January 7, 2021 - 4:30:06 PM



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⟩



Record views