Synthesising Succinct Strategies in Safety Games?

Abstract. Finite turn-based safety games have been used for very dif-ferent problems such as the synthesis of linear temporal logic (LTL) [8], the synthesis of schedulers for computer systems running on multiproces-sor platforms [4], and also for the determinisation of timed automata [3]. In these contexts, games are implicitly defined, and their size is at least exponential in the size of the input. Nevertheless, there are natural re-lations between states of arenas of such games. We first formalise the properties that we expect on the relation between states, thanks to the notion of alternating simulation. Then, we show how such simulations can be exploited to (1) improve the running time of the OTFUR algorithm[6] to compute winning strategies and (2) obtain a succinct representation of a winning strategy. We also show that our general theory applies to the three applications mentioned above.