Stochastic Games with Lossy Channels

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

doi:10.1007/978-3-540-78499-9_4

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 proceeding › Conference 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 language	English
Title of host publication	Foundations of Software Science and Computational Structures
Subtitle of host publication	11th 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
Publisher	Springer Berlin Heidelberg
Pages	35-49
Number of pages	15
Volume	4962
ISBN (Electronic)	978-3-540-78499-9
ISBN (Print)	978-3-540-78497-5
DOIs	https://doi.org/10.1007/978-3-540-78499-9_4
Publication status	Published - 2008

Access to Document

10.1007/978-3-540-78499-9_4

Abdulla Henda ET AL 2008 Stochastic Games with Lossy ChannelsAccepted author manuscript, 225 KB

http://dx.doi.org/10.1007/978-3-540-78499-9_4

Cite this

Abdulla, P. A., Henda, N. B., Alfaro, L. D., Mayr, R., & Sandberg, S. (2008). Stochastic Games with Lossy Channels. In Foundations of Software Science and Computational Structures: 11th 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 (Vol. 4962, pp. 35-49). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-78499-9_4

Abdulla, Parosh Aziz ; Henda, Noomene Ben ; Alfaro, Luca de et al. / Stochastic Games with Lossy Channels. Foundations of Software Science and Computational Structures: 11th 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. Vol. 4962 Springer Berlin Heidelberg, 2008. pp. 35-49

@inproceedings{ed80cd63a6de4cc5a411f28bd34e44dc,

title = "Stochastic Games with Lossy Channels",

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{\"u}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].",

author = "Abdulla, {Parosh Aziz} and Henda, {Noomene Ben} and Alfaro, {Luca de} and Richard Mayr and Sven Sandberg",

year = "2008",

doi = "10.1007/978-3-540-78499-9_4",

language = "English",

isbn = "978-3-540-78497-5",

volume = "4962",

pages = "35--49",

booktitle = "Foundations of Software Science and Computational Structures",

publisher = "Springer Berlin Heidelberg",

}

Abdulla, PA, Henda, NB, Alfaro, LD, Mayr, R & Sandberg, S 2008, Stochastic Games with Lossy Channels. in Foundations of Software Science and Computational Structures: 11th 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. vol. 4962, Springer Berlin Heidelberg, pp. 35-49. https://doi.org/10.1007/978-3-540-78499-9_4

Stochastic Games with Lossy Channels. / Abdulla, Parosh Aziz; Henda, Noomene Ben; Alfaro, Luca de et al.

Foundations of Software Science and Computational Structures: 11th 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. Vol. 4962 Springer Berlin Heidelberg, 2008. p. 35-49.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Stochastic Games with Lossy Channels

AU - Abdulla, Parosh Aziz

AU - Henda, Noomene Ben

AU - Alfaro, Luca de

AU - Mayr, Richard

AU - Sandberg, Sven

PY - 2008

Y1 - 2008

N2 - 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].

AB - 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].

U2 - 10.1007/978-3-540-78499-9_4

DO - 10.1007/978-3-540-78499-9_4

M3 - Conference contribution

SN - 978-3-540-78497-5

VL - 4962

SP - 35

EP - 49

BT - Foundations of Software Science and Computational Structures

PB - Springer Berlin Heidelberg

ER -

Abdulla PA, Henda NB, Alfaro LD, Mayr R, Sandberg S. Stochastic Games with Lossy Channels. In Foundations of Software Science and Computational Structures: 11th 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. Vol. 4962. Springer Berlin Heidelberg. 2008. p. 35-49 https://doi.org/10.1007/978-3-540-78499-9_4

Stochastic Games with Lossy Channels

Abstract

Access to Document

Fingerprint

Cite this