论文标题
从准主任到进步措施
From Quasi-Dominions to Progress Measures
论文作者
论文摘要
我们根据进度措施重新审视了平等游戏解决方案的方法，并展示了如何与这些方法集成了准统治的概念。这个想法是，尽管基于进度措施的技术通常集中在两个玩家之一上，但在解决方案过程中，几乎没有收集有关另一个玩家的信息。添加准统治提供了有关该玩家的其他信息，可以将其利用以极大地加速融合到进度度量。但是，为了容纳准统治，必须对方法进行非微不足道的改进。特别是，我们需要引入一种新颖的度量概念和一种新方法来证明所得解决方案技术的正确性。
We revisit the approaches to the solution of parity games based on progress measures and show how the notion of quasi dominions can be integrated with those approaches. The idea is that, while progress measure based techniques typically focus on one of the two players, little information is gathered on the other player during the solution process. Adding quasi dominions provides additional information on this player that can be leveraged to greatly accelerate convergence to a progress measure. To accommodate quasi dominions, however, non trivial refinements of the approach are necessary. In particular, we need to introduce a novel notion of measure and a new method to prove correctness of the resulting solution technique.
