Solving Counter Parity Games

Abstract We study a class of parity games equipped with counters that evolve according to arbitrary non-negative affine functions. These games capture several cost models for dynamic systems from the literature. We present an elementary algorithm for computing the exact value of a counter parity game, which both generalizes previous results and improves their complexity. To this end, we introduce a class of ω -regular games with imperfect information and imperfect recall, solve them using automata-based techniques, and prove a correspondence between finite-memory strategies in such games and strategies in counter parity games.

Authors

• Dietmar Berwanger
• Lukasz Kaiser
• Simon Leßenich

Keywords

No keywords are indexed for this paper.