Cristau, Julien; David, Claire; Horn, FlorianISTA
Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.
Proceedings of GandALF 2010
30 - 39
GandALF: Games, Automata, Logic, and Formal Verification
Minori, Amalfi Coast, Italy
2010-06-17 – 2010-06-18
Cristau J, David C, Horn F. How do we remember the past in randomised strategies? . In: Proceedings of GandALF 2010. Vol 25. Open Publishing Association; 2010:30-39. doi:10.4204/EPTCS.25.7
Cristau, J., David, C., & Horn, F. (2010). How do we remember the past in randomised strategies? . In Proceedings of GandALF 2010 (Vol. 25, pp. 30–39). Minori, Amalfi Coast, Italy: Open Publishing Association. https://doi.org/10.4204/EPTCS.25.7
Cristau, Julien, Claire David, and Florian Horn. “How Do We Remember the Past in Randomised Strategies? .” In Proceedings of GandALF 2010, 25:30–39. Open Publishing Association, 2010. https://doi.org/10.4204/EPTCS.25.7.
J. Cristau, C. David, and F. Horn, “How do we remember the past in randomised strategies? ,” in Proceedings of GandALF 2010, Minori, Amalfi Coast, Italy, 2010, vol. 25, pp. 30–39.
Cristau J, David C, Horn F. 2010. How do we remember the past in randomised strategies? . Proceedings of GandALF 2010. GandALF: Games, Automata, Logic, and Formal Verification, EPTCS, vol. 25, 30–39.
Cristau, Julien, et al. “How Do We Remember the Past in Randomised Strategies? .” Proceedings of GandALF 2010, vol. 25, Open Publishing Association, 2010, pp. 30–39, doi:10.4204/EPTCS.25.7.