Search

• < Previous
• 1
• Next >

---

Solving Simple Stochastic Games with Few Random Vertices

Hugo Gimbert ; Florian Horn.

Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the existence of optimal permutation strategies, a&nbsp;[&hellip;]

---

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 memory states of a strategy ensuring a safety objective is given by the size of the maximal antichain of left quotients&nbsp;[&hellip;]

---