- Abstract:
-
We give an algorithm for solving stochastic parity games with almost-sure winning conditions on lossy channel systems, for the case where the players are restricted to finite-memory strategies. First, we describe a general framework, where we consider the class of 2.5-player games with almost-sure parity winning conditions on possibly infinite game graphs, assuming that the game contains a finite attractor. An attractor is a set of states (not necessarily absorbing) that is almost surely re-visited regardless of the players' decisions. We present a scheme that characterizes the set of winning states for each player. Then, we instantiate this scheme to obtain an algorithm for stochastic game lossy channel systems.
- Links To Paper
- Full version including all proofs
- Bibtex format
- @InProceedings{EDI-INF-RR-1416,
- author = {
Richard Mayr
and Parosh Aziz Abdulla
and Lorenzo Clemente
and Sven Sandberg
},
- title = {Stochastic Parity Games on Lossy Channel Systems},
- book title = {10th International Conference on Quantitative Evaluation of SysTems (QEST 2013)},
- year = 2013,
- month = {Aug},
- pages = {19},
- url = {http://arxiv.org/abs/1305.5228},
- }
|
