Playing Safe, Ten Years Later

Thomas Colcombet, Nathanaël Fijalkow, Florian Horn

We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety objectives. More specifically, we show that the minimal number of me…