Permissive strategies: from parity games to safety games

DOI10.1051/ita:2002013zbMath1090.91514OpenAlexW2120967289MaRDI QIDQ4800258

Julien Bernet, David Janin, Igor Walukiewicz

Publication date: 2002

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2002__36_3_261_0

Mathematics Subject Classification ID

Discrete-time games (91A50) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (20)

Measuring Permissivity in Finite Games ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Shield synthesis ⋮ Poster Abstract: Permissiveness for Strategy Adaptation ⋮ Strategy construction for parity games with imperfect information ⋮ Unnamed Item ⋮ Down the Borel hierarchy: solving Muller games via safety games ⋮ Indecision and delays are the parents of failure -- taming them algorithmically by synthesizing delay-resilient control ⋮ Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems ⋮ Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints ⋮ Assume-admissible synthesis ⋮ Strategy synthesis for multi-dimensional quantitative objectives ⋮ Computing Weakest Strategies for Safety Games of Imperfect Information ⋮ On satisficing in quantitative games ⋮ Synthesizing Optimally Resilient Controllers ⋮ Synthesizing optimally resilient controllers ⋮ A Compositional Framework for Controller Synthesis ⋮ Logical time control of concurrent DES ⋮ Bounded game-theoretic semantics for modal mu-calculus ⋮ Compositional construction of most general controllers

Uses Software

• UMDES

Cites Work

• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Hierarchies of weak automata and weak monadic formulas
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• The complexity of mean payoff games on graphs
• Games for synthesis of controllers with partial observation.
• State-strategies for games in F_σδ ∩ G_δσ
• A unified approach to control problems in discrete event processes
• On the synthesis of strategies in infinite games
• An automata-theoretic approach to branching-time model checking
• On model checking for the \(\mu\)-calculus and its fragments
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Permissive strategies: from parity games to safety games