文章基本信息

标题：Stochastic Parity Games on Lossy Channel Systems
本地全文：下载
作者：Parosh Abdulla ; Lorenzo Clemente ; Richard Mayr 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2014
卷号：10
期号：4
页码：1
DOI：10.2168/LMCS-10(4:21)2014
出版社：Technical University of Braunschweig
摘要：We give an algorithm for solving stochastic parity games with almost-sure winning conditions on {\it lossy channel systems}, under the constraint that both players are restricted to finite-memory strategies. First, we describe a general framework, where we consider the class of 2 1/2-player games with almost-sure parity winning conditions on possibly infinite game graphs, assuming that the game contains a {\it 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 {\it stochastic game lossy channel systems}.
其他关键词：Stochastic games; Lossy channel systems; Finite attractor; Parity games; Memoryless determinacy.