Collapsible Pushdown Parity Games
Collapsible Pushdown Parity Games
复制标题
可折叠下推平价游戏
DOI：
10.1145/3457214
复制
发表时间：
2021
影响因子：
0.5
通讯作者：
Broadbent C
中科院分区：
文献类型：
--
作者：
Broadbent C
本文研究了无限图上一大类基于完全信息回合的两人完全信息对等对策，即由可折叠下推自动机生成的对策。研究这些博弈的主要动机来自于可折叠下推自动机和高阶递归方案的联系，这两个模型对于生成无限树都是等价的。我们的主要结果是建立这种游戏的可判断性，并提供获胜地区以及获胜战略的有效代表。因此，本文的结果为深入研究由可折叠下推自动机/递归方案生成的树的逻辑性质提供了所有必要的工具。
This article studies a large class of two-player perfect-information turn-based parity games on infinite graphs, namely, those generated by collapsible pushdown automata. The main motivation for studying these games comes from the connections from collapsible pushdown automata and higher-order recursion schemes, both models being equi-expressive for generating infinite trees. Our main result is to establish the decidability of such games and to provide an effective representation of the winning region as well as of a winning strategy. Thus, the results obtained here provide all necessary tools for an in-depth study of logical properties of trees generated by collapsible pushdown automata/recursion schemes.
登录
查看更多内容
依赖树自动机
DOI：
10.1007/978-3-642-00596-1_8
发表时间：
2009
期刊：
Inf. Comput.
影响因子：
--
作者：
C. Stirling
通讯作者：
C. Stirling
可折叠下推自动机和递归方案
DOI：
10.1145/3091122
发表时间：
2008
期刊：
2008 23rd Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
M. Hague;A. Murawski;C. Ong;O. Serre
通讯作者：
O. Serre
DOI：
10.1016/0304-3975(85)90087-8
发表时间：
1985
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
D. E. Muller;P. Schupp
通讯作者：
D. E. Muller;P. Schupp
以游戏为背景的风景
DOI：
10.1109/lics.2004.1319630
发表时间：
2004
期刊：
Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004.
影响因子：
--
作者：
Igor Walukiewicz
通讯作者：
Igor Walukiewicz
DOI：
10.2168/lmcs-4(4:14)2008
发表时间：
2007
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
M. Hague;C. Ong
通讯作者：
C. Ong