HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Random Fruits on the Zielonka Tree

Abstract : 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.
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, February 12, 2009 - 11:23:05 AM
Last modification on : Wednesday, December 20, 2017 - 5:42:07 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 10:18:10 PM


Files produced by the author(s)


  • HAL Id : inria-00360829, version 1
  • ARXIV : 0902.2736



Florian Horn. Random Fruits on the Zielonka Tree. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. pp.541-552. ⟨inria-00360829⟩



Record views


Files downloads