The Rabin index of parity games: Its complexity and approximation
The Rabin index of parity games: Its complexity and approximation
复制标题
平价游戏的拉宾指数：其复杂性和近似值
DOI：
10.1016/j.ic.2015.06.005
复制
发表时间：
2015
影响因子：
1
通讯作者：
Huth M
中科院分区：
文献类型：
--
作者：
Huth M
我们研究的描述性的复杂性，考虑到他们的游戏图的着色，而忽略了他们的所有权结构的平价游戏。有色博弈图被识别，如果它们确定相同的获胜区域和策略，对于所有的所有权结构的节点。奇偶对策的Rabin指数是所有等价着色函数的最大色的最小值。我们表明，决定拉宾指数是否至少是k是在PTIME为k=1，但NP-困难的所有固定的k > 1。我们提出了一个EXPTIME算法，通过简化其输入着色函数来计算拉宾指数。该算法用循环检测代替简单循环时，其输出在多项式时间内过逼近Rabin指数。实验结果表明，这种近似在实际中得到了很好的结果。
We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colored game graphs are identified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in PTIME for k=1 but NP-hard for all fixed k > 1. We present an EXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output over-approximates the Rabin index in polynomial time. Experimental results show that this approximation yields good values in practice.
登录
查看更多内容
DOI：
10.1016/s0019-9958(79)90653-3
发表时间：
1979-11
期刊：
Inf. Control.
影响因子：
--
作者：
K. Wagner
通讯作者：
K. Wagner
PGSolver 奇偶游戏求解器集合版本 3
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Oliver Friedmann;M. Lange
通讯作者：
M. Lange
计算奇偶校验自动机的拉宾指数
DOI：
--
发表时间：
1999
期刊：
RAIRO - Theoretical Informatics and Applications
影响因子：
--
作者：
Olivier Carton;Ramón Maceiras
通讯作者：
Ramón Maceiras
平价游戏中的致命吸引力
DOI：
--
发表时间：
2013
期刊：
Foundations of Software Science and Computation Structure
影响因子：
--
作者：
M. Huth;Jim Huan;Nir Piterman
通讯作者：
Nir Piterman