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

lmcs:944 - Logical Methods in Computer Science, January 5, 2015, Volume 10, Issue 4
Stochastic Parity Games on Lossy Channel Systems

Authors: Abdulla, Parosh Aziz and Clemente, Lorenzo and Mayr, Richard and Sandberg, Sven

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}.


Source : oai:arXiv.org:1410.4448
DOI : 10.2168/LMCS-10(4:21)2014
Volume: Volume 10, Issue 4
Published on: January 5, 2015
Submitted on: January 19, 2014
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 67 times.
This article's PDF has been downloaded 55 times.