A survey of stochastic ω-regular games

被引：88
|
作者：
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
相关论文
共 50 条
  • [1] A survey of partial-observation stochastic parity games
    Chatterjee, Krishnendu
    Doyen, Laurent
    Henzinger, Thomas A.
    FORMAL METHODS IN SYSTEM DESIGN, 2013, 43 (02) : 268 - 284
  • [2] The complexity of stochastic Muller games
    Chatterjee, Krishnendu
    INFORMATION AND COMPUTATION, 2012, 211 : 29 - 48
  • [3] Stochastic games
    Solan, Eilon
    Vieille, Nicolas
    PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2015, 112 (45) : 13743 - 13746
  • [4] Comparison of algorithms for simple stochastic games
    Kretinsky, Jan
    Ramneantu, Emanuel
    Slivinskiy, Alexander
    Weininger, Maximilian
    INFORMATION AND COMPUTATION, 2022, 289
  • [5] A survey of partial-observation stochastic parity games
    Krishnendu Chatterjee
    Laurent Doyen
    Thomas A. Henzinger
    Formal Methods in System Design, 2013, 43 : 268 - 284
  • [6] Recursive Markov Decision Processes and Recursive Stochastic Games
    Etessami, Kousha
    Yannakakis, Mihalis
    JOURNAL OF THE ACM, 2015, 62 (02)
  • [7] Stochastic shortest path games
    Patek, SD
    Bertsekas, DP
    SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1999, 37 (03) : 804 - 824
  • [8] Automatizability and Simple Stochastic Games
    Huang, Lei
    Pitassi, Toniann
    AUTOMATA, LANGUAGES AND PROGRAMMING, ICALP, PT I, 2011, 6755 : 605 - 617
  • [9] Stochastic Games with Synchronization Objectives
    Doyen, Laurent
    JOURNAL OF THE ACM, 2023, 70 (03)
  • [10] Regular potential games
    Swenson, Brian
    Murray, Ryan
    Kar, Soummya
    GAMES AND ECONOMIC BEHAVIOR, 2020, 124 : 432 - 453
12345