We consider algorithms for parity games that use attractor decomposition, such as Zielonka’s recursive algorithm, priority promotion, and tangle learning. In earlier work, we identified the Two Counters parity game family that requires exponential time for many algorithms, including attractor decomposition algorithms, and we identified the main mechanism that slows down parity game algorithms as so-called distractions. We observe a fundamentally different approach in avoiding distractions between algorithms that use attractor decomposition and algorithms that compute progress measures. We now propose an alternative attractor-based method to avoid distractions by applying the attractor decomposition recursively. We demonstrate that this algorithm solves the Two Counters games efficiently, but that a modification of the Two Counters method can also delay the recursive algorithm exponentially.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Avoiding Distractions in Parity Games

  • Tom van Dijk

摘要

We consider algorithms for parity games that use attractor decomposition, such as Zielonka’s recursive algorithm, priority promotion, and tangle learning. In earlier work, we identified the Two Counters parity game family that requires exponential time for many algorithms, including attractor decomposition algorithms, and we identified the main mechanism that slows down parity game algorithms as so-called distractions. We observe a fundamentally different approach in avoiding distractions between algorithms that use attractor decomposition and algorithms that compute progress measures. We now propose an alternative attractor-based method to avoid distractions by applying the attractor decomposition recursively. We demonstrate that this algorithm solves the Two Counters games efficiently, but that a modification of the Two Counters method can also delay the recursive algorithm exponentially.