This work is licensed under the Creative Commons Attribution-No Derivative Works License. Sparse Positional Strategies for Safety Games∗

We consider the problem of obtaining sparse positional strategies for safety games. Such games are a commonly used model in many formal methods, as they make the interaction of a system with its environment explicit. Example applications are the synthesis of finite-state systems from specifications in temporal logic and alternating-time temporal logic (ATL) model checking. Often, a winning strategy for one of the players is used as a certificate or as an artefact for further processing in the application. Small such certificates, i.e., strategies that can be written down very compactly, are typically preferred. For safety games, we only need to consider positional strategies. These map game positions of a player onto a move that is to be taken by the player whenever the play enters that position. For representing positional strategies compactly, a common goal is to minimize the number of positions for which a winning player’s move needs to be defined such that the game is still won by the same player, without visiting a position with an undefined next move. We call winning strategies in which the next move is defined for few of the player’s positions sparse. From a sparse winning positional strategy for the safety player in a synthesis game, we can compute a small implementation satisfying the specification used for building the game, and for ATL model checking, sparse strategies are easier to comprehend and thus help in analysing the cause of a model checking result