Abstract | ||
---|---|---|
We give an algorithm for solving stochastic parity games with almost-sure winning conditions on lossy channel systems, for the case where the players are restricted to finite-memory strategies. First, we describe a general framework, where we consider the class of $2\frac{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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-40196-1_29 | Logical Methods in Computer Science |
Keywords | DocType | Volume |
infinite game graph,almost-sure parity,finite attractor,stochastic parity game,lossy channel system,general framework,stochastic game lossy channel,player game | Journal | 10 |
Issue | ISSN | Citations |
4 | Logical Methods in Computer Science, Volume 10, Issue 4 (January
5, 2015) lmcs:944 | 3 |
PageRank | References | Authors |
0.41 | 24 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Parosh Aziz Abdulla | 1 | 2010 | 122.22 |
Lorenzo Clemente | 2 | 114 | 9.24 |
Richard Mayr | 3 | 389 | 22.29 |
Sven Sandberg | 4 | 140 | 9.64 |