Stochastic Parity Games on Lossy Channel Systems

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

Research output: Contribution to journalArticlepeer-review

Abstract

We give an algorithm for solving stochastic parity games with almost-sure winning conditions on 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 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
Article number21
Number of pages21
JournalLogical Methods in Computer Science
Volume10
Issue number4
DOIs
Publication statusPublished - Jan 2015

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

Cite this