• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Winning Cores in Parity Games
【24h】

Winning Cores in Parity Games

机译：奇偶游戏的制胜核心

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We introduce the novel notion of winning cores in parity games and develop a deterministic polynomial-time under-approximation algorithm for solving parity games based on winning core approximation. Underlying this algorithm are a number properties about winning cores which are interesting in their own right. In particular, we show that the winning core and the winning region for a player in a parity game are equivalently empty. Moreover, the winning core contains all fatal attractors but is not necessarily a dominion itself. Experimental results are very positive both with respect to quality of approximation and running time. It outperforms existing state-of-the-art algorithms significantly on most benchmarks.
机译：我们介绍了奇偶游戏中获胜核心的新颖概念，并开发了一种确定性多项式时间欠逼近算法，用于基于获胜核心逼近来求解奇偶游戏。该算法的基础是有关获胜核心的许多属性，这些属性本身就是有趣的。尤其是，我们证明了平价游戏中玩家的获胜核心和获胜区域均是空的。而且，获胜的核心包含所有致命的吸引子，但本身并不一定是统治者。在逼近质量和运行时间方面，实验结果都是非常积极的。在大多数基准测试中，它的性能明显优于现有的最新算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号