article published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Luca De Alfaro author Thomas A Henzinger author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724 KrCh department ToHe department Rigorous Systems Engineering project Microsoft Research Faculty Fellowship project We consider two-player games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We consider ω-regular winning conditions specified as parity objectives. Both players are allowed to use randomization when choosing their moves. We study the computation of the limit-winning set of states, consisting of the states where the sup-inf value of the game for player 1 is 1: in other words, a state is limit-winning if player 1 can ensure a probability of winning arbitrarily close to 1. We show that the limit-winning set can be computed in O(n2d+2) time, where n is the size of the game structure and 2d is the number of priorities (or colors). The membership problem of whether a state belongs to the limit-winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games. This is because concurrent games do not satisfy two of the most fundamental properties of turn-based parity games. First, in concurrent games limit-winning strategies require randomization; and second, they require infinite memory. ACM2011 eng 00029620230000610.1145/1970398.1970404 124 https://research-explorer.ista.ac.at/record/2054 K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Qualitative concurrent parity games,” <i>ACM Transactions on Computational Logic</i>, vol. 12, no. 4. ACM, 2011. Chatterjee, Krishnendu, et al. “Qualitative Concurrent Parity Games.” <i>ACM Transactions on Computational Logic</i>, vol. 12, no. 4, 28, ACM, 2011, doi:<a href="https://doi.org/10.1145/1970398.1970404">10.1145/1970398.1970404</a>. Chatterjee K, De Alfaro L, Henzinger TA. Qualitative concurrent parity games. <i>ACM Transactions on Computational Logic</i>. 2011;12(4). doi:<a href="https://doi.org/10.1145/1970398.1970404">10.1145/1970398.1970404</a> Chatterjee K, De Alfaro L, Henzinger TA. 2011. Qualitative concurrent parity games. ACM Transactions on Computational Logic. 12(4), 28. K. Chatterjee, L. De Alfaro, T.A. Henzinger, ACM Transactions on Computational Logic 12 (2011). Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2011). Qualitative concurrent parity games. <i>ACM Transactions on Computational Logic</i>. ACM. <a href="https://doi.org/10.1145/1970398.1970404">https://doi.org/10.1145/1970398.1970404</a> Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Qualitative Concurrent Parity Games.” <i>ACM Transactions on Computational Logic</i>. ACM, 2011. <a href="https://doi.org/10.1145/1970398.1970404">https://doi.org/10.1145/1970398.1970404</a>. 33542018-12-11T12:02:51Z2026-07-07T14:02:38Z