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

Abstract

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
Pages35-49
Number of pages15
Volume4962
ISBN (Electronic)978-3-540-78499-9
ISBN (Print)978-3-540-78497-5
DOIs
Publication statusPublished - 2008

Fingerprint

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

Cite this