2026-07-22T06:37:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1848 2024-03-06T10:33:13Z ddc:004 open_access

Random Fruits on the Zielonka Tree Horn, Florian Model checking Controller synthesis Stochastic games Randomisation Stochastic games are a natural model for the synthesis of controllers confronted to adversarial and/or random actions. In particular, $\omega$-regular games of infinite length can represent reactive systems which are not expected to reach a correct state, but rather to handle a continuous stream of events. One critical resource in such applications is the memory used by the controller. In this paper, we study the amount of memory that can be saved through the use of randomisation in strategies, and present matching upper and lower bounds for stochastic Muller games. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Horn 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1848 urn:nbn:de:0030-drops-18489 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1848 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode