Stochastic Parity Games on Lossy Channel Systems
2014 (English)In: Logical Methods in Computer Science, ISSN 1860-5974, Vol. 10, no 4, 21Article in journal (Refereed) Published
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 finitememory strategies. First, we describe a general framework, where we consider the class of 21/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.
Place, publisher, year, edition, pages
2014. Vol. 10, no 4, 21
Stochastic games, Lossy channel systems, Finite attractor, Parity games, Memoryless determinacy
IdentifiersURN: urn:nbn:se:uu:diva-248657DOI: 10.2168/LMCS-10(4:21)2014ISI: 000350399900001Archive number: 10.2168/LMCS-10OAI: oai:DiVA.org:uu-248657DiVA: diva2:802274