2013 | OriginalPaper | Chapter
Stochastic Parity Games on Lossy Channel Systems
Authors : Parosh Aziz Abdulla, Lorenzo Clemente, Richard Mayr, Sven Sandberg
Published in: Quantitative Evaluation of Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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\frac{1}{2}$
-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
.