Stochastic Parity Games on Lossy Channel Systems

Parosh Aziz Abdulla, Lorenzo Clemente, Richard Mayr, Sven Sandberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 TeX-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.
Original languageEnglish
Title of host publicationQuantitative Evaluation of Systems
Subtitle of host publication10th International Conference, QEST 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings
Number of pages17
ISBN (Electronic)978-3-642-40196-1
Publication statusPublished - 2013


Dive into the research topics of 'Stochastic Parity Games on Lossy Channel Systems'. Together they form a unique fingerprint.

Cite this