Succinct progress measures for solving parity games
Succinct progress measures for solving parity games
复制标题
解决平价游戏的简洁进度措施
DOI：
10.1109/lics.2017.8005092
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Lazic
中科院分区：
文献类型：
--
作者：
M. Jurdzinski;R. Lazic
Calude等人最近的突破性论文。已经提供了第一种用于在准多项式时间求解平等游戏的算法，那里最好的算法是轻度的次指数。我们根据进度度量设计了一种替代的准多项式时间算法，这使我们能够将准多项式所需的空间减少到几乎线性。我们的关键技术工具是有序的树编码的新颖概念，以及我们使用有限的自适应多表演者证明的简洁的树编码结果，它们本身都很有趣。
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.
DOI：
10.1007/s10009-019-00509-3
发表时间：
2019-06-01
影响因子：
1.5
作者：
Fearnley, John;Jain, Sanjay;Wojtczak, Dominik
通讯作者：
Wojtczak, Dominik