---
_id: '3354'
abstract:
- lang: eng
  text: '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.'
article_number: '28'
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Luca
  full_name: De Alfaro, Luca
  last_name: De Alfaro
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: Chatterjee K, De Alfaro L, Henzinger TA. 2011. Qualitative concurrent parity
    games. ACM Transactions on Computational Logic. 12(4), 28.
  mla: 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>.
  short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, ACM Transactions on Computational
    Logic 12 (2011).
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T12:02:51Z
date_published: 2011-07-04T00:00:00Z
date_updated: 2026-07-07T14:02:38Z
day: '04'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1145/1970398.1970404
external_id:
  isi:
  - '000296202300006'
intvolume: '        12'
isi: 1
issue: '4'
language:
- iso: eng
month: '07'
oa_version: None
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: ACM Transactions on Computational Logic
publication_status: published
publisher: ACM
publist_id: '3262'
quality_controlled: '1'
related_material:
  record:
  - id: '2054'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Qualitative concurrent parity games
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2011'
...