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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.541-552, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00360829
Contributeur : Publications Loria <>
Soumis le : jeudi 12 février 2009 - 11:23:05
Dernière modification le : mercredi 20 décembre 2017 - 17:42:07
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:18:10

Fichiers

Horn_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Florian Horn. Random Fruits on the Zielonka Tree. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.541-552, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360829〉

Partager

Métriques

Consultations de la notice

66

Téléchargements de fichiers

87