License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1848
URN: urn:nbn:de:0030-drops-18489
URL: http://drops.dagstuhl.de/opus/volltexte/2009/1848/
Go to the corresponding Portal


Horn, Florian

Random Fruits on the Zielonka Tree

pdf-format:
Document 1.pdf (271 KB)


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.

BibTeX - Entry

@InProceedings{horn:LIPIcs:2009:1848,
  author =	{Florian Horn},
  title =	{{Random Fruits on the Zielonka Tree}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{541--552},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1848},
  URN =		{urn:nbn:de:0030-drops-18489},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1848},
  annote =	{Keywords: Model checking, Controller synthesis, Stochastic games, Randomisation}
}

Keywords: Model checking, Controller synthesis, Stochastic games, Randomisation
Seminar: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI