A survey of stochastic ω-regular games

被引：95
作者：
Chatterjee, Krishnendu [1 ]
Henzinger, Thomas A. [1 ]
机构：
[1] Ecole Polytech Fed Lausanne, Lausanne, Switzerland
来源：
JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2012年 / 78卷 / 02期
关键词：
Game theory; Stochastic games; omega-Regular objectives; STRATEGY IMPROVEMENT; INFINITE GAMES; COMPLEXITY; RABIN; ALGORITHMS;
D O I：
10.1016/j.jcss.2011.05.002
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We summarize classical and recent results about two-player games played on graphs with omega-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications. (C) 2011 Elsevier Inc. All rights reserved.
引用
收藏
页码：394 / 413
页数：20
相关论文
共 96 条
[1]  
ABADI M, 1989, LECT NOTES COMPUT SC, V372, P1
[2]   Alternating-time temporal logic [J].
Alur, R ;
Henzinger, TA ;
Kupferman, O .
JOURNAL OF THE ACM, 2002, 49 (05) :672-713
[3]  
Alur R, 1998, LECT NOTES COMPUT SC, V1466, P163, DOI 10.1007/BFb0055622
[4]  
[Anonymous], 1997, PhD thesis
[5]  
[Anonymous], 1992, TEMPORAL LOGIC REACT, DOI DOI 10.1007/978-1-4612-0931-7
[6]  
[Anonymous], 2004, P 15 ANN ACM SIAM S
[7]  
[Anonymous], 2001, LNCS, DOI [DOI 10.1007/3-540-45449-7_11, DOI 10.1007/3-540-45449-711]
[8]  
[Anonymous], 2000, CAV'00, LNCS 1855
[9]  
[Anonymous], 1982, Game theory
[10]  
[Anonymous], 1989, C RECORD 16 ANN ACM, DOI [DOI 10.1145/75277.75293, 10.1145/75277.75293]
12345678910