文章基本信息

标题：Random Fruits on the Zielonka Tree
本地全文：下载
作者：Florian Horn
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：3
页码：541-552
DOI：10.4230/LIPIcs.STACS.2009.1848
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Model checking; Controller synthesis; Stochastic games; Randomisation