Stochastic Games with Lossy Channels

Parosh Aziz Abdulla, Noomene Ben Henda, Luca de Alfaro, Richard Mayr, Sven Sandberg

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


We consider turn-based stochastic games on infinite graphs induced by game probabilistic lossy channel systems (GPLCS), the game version of probabilistic lossy channel systems (PLCS). We study games with Büchi (repeated reachability) objectives and almost-sure winning conditions. These games are pure memoryless determined and, under the assumption that the target set is regular, a symbolic representation of the set of winning states for each player can be effectively constructed. Thus, turn-based stochastic games on GPLCS are decidable. This generalizes the decidability result for PLCS-induced Markov decision processes in [10].
Original languageEnglish
Title of host publicationFoundations of Software Science and Computational Structures
Subtitle of host publication11th International Conference, FOSSACS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29 - April 6, 2008. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-540-78499-9
ISBN (Print)978-3-540-78497-5
Publication statusPublished - 2008


Dive into the research topics of 'Stochastic Games with Lossy Channels'. Together they form a unique fingerprint.

Cite this