Solving Stochastic Büchi Games on Infinite Arenas with a Finite Attractor

Nathalie Bertrand
(Inria Rennes Bretagne Atlantique)
Philippe Schnoebelen
(LSV, CNRS and ENS Cachan)

We consider games played on an infinite probabilistic arena where the first player aims at satisfying generalized Büchi objectives almost surely, i.e., with probability one. We provide a fixpoint characterization of the winning sets and associated winning strategies in the case where the arena satisfies the finite-attractor property. From this we directly deduce the decidability of these games on probabilistic lossy channel systems.

In Luca Bortolussi and Herbert Wiklicky: Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2013), Rome, 23rd-24th March 2013, Electronic Proceedings in Theoretical Computer Science 117, pp. 116–131.
Published: 11th June 2013.

ArXived at: https://dx.doi.org/10.4204/EPTCS.117.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org