Parosh Aziz Abdulla ; Lorenzo Clemente ; Richard Mayr ; Sven Sandberg - Stochastic Parity Games on Lossy Channel Systems

lmcs:944 - Logical Methods in Computer Science, January 5, 2015, Volume 10, Issue 4 - https://doi.org/10.2168/LMCS-10(4:21)2014
Stochastic Parity Games on Lossy Channel SystemsArticle

Authors: Parosh Aziz Abdulla ; Lorenzo Clemente ; Richard Mayr ; Sven Sandberg

    We give an algorithm for solving stochastic parity games with almost-sure winning conditions on {\it lossy channel systems}, under the constraint that both players are restricted to finite-memory strategies. First, we describe a general framework, where we consider the class of 2 1/2-player games with almost-sure parity winning conditions on possibly infinite game graphs, assuming that the game contains a {\it 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 {\it stochastic game lossy channel systems}.


    Volume: Volume 10, Issue 4
    Published on: January 5, 2015
    Imported on: January 19, 2014
    Keywords: Computer Science - Logic in Computer Science

    1 Document citing this article

    Consultation statistics

    This page has been seen 1208 times.
    This article's PDF has been downloaded 327 times.