---
_id: '4627'
abstract:
- lang: eng
  text: 'We consider two-player games, which are played on a finite state space for
    an infinite number of rounds. The games are concurrent, that is, in each round,
    the two players choose their moves independently and simultaneously; the current
    state and the two moves determine a successor state. We consider omega-regular
    winning conditions on the resulting infinite state sequence. To model the independent
    choice of moves, both players are allowed to use randomization for selecting their
    moves. This gives rise to the following qualitative modes of winning, which can
    be studied without numerical considerations concerning probabilities: sure-win
    (player 1 can ensure winning with certainty), almost-sure-win (player 1 can ensure
    winning with probability 1), limit-win (player 1 can ensure winning with probability
    arbitrarily close to 1), bounded-win (player 1 can ensure winning with probability
    bounded away from 0), positive-win (player 1 can ensure winning with positive
    probability), and exist-win (player 1 can ensure that at least one possible outcome
    of the game satisfies the winning condition).We provide algorithms for computing
    the sets of winning states for each of these winning modes. In particular, we
    solve concurrent Rabin-chain games in n0 (m) time, where n is the size of the
    game structure and m is the number of pairs in the Rabin-chain condition. While
    this complexity is in line with traditional turn-based 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 are. This is because concurrent
    games violate two of the most fundamental properties of turn-based games. First,
    concurrent games are not determined, but rather exhibit a more general duality
    property, which involves multiple modes of winning. Second, winning strategies
    for concurrent games may require infinite memory.'
article_processing_charge: No
author:
- 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: 'De Alfaro L, Henzinger TA. Concurrent omega-regular games. In: <i>Proceedings
    of the 15th Annual IEEE Symposium on Logic in Computer Science</i>. IEEE; 2000:141-154.
    doi:<a href="https://doi.org/10.1109/LICS.2000.855763">10.1109/LICS.2000.855763</a>'
  apa: 'De Alfaro, L., &#38; Henzinger, T. A. (2000). Concurrent omega-regular games.
    In <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i>
    (pp. 141–154). Santa Barbara, CA, USA: IEEE. <a href="https://doi.org/10.1109/LICS.2000.855763">https://doi.org/10.1109/LICS.2000.855763</a>'
  chicago: De Alfaro, Luca, and Thomas A Henzinger. “Concurrent Omega-Regular Games.”
    In <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i>,
    141–54. IEEE, 2000. <a href="https://doi.org/10.1109/LICS.2000.855763">https://doi.org/10.1109/LICS.2000.855763</a>.
  ieee: L. De Alfaro and T. A. Henzinger, “Concurrent omega-regular games,” in <i>Proceedings
    of the 15th Annual IEEE Symposium on Logic in Computer Science</i>, Santa Barbara,
    CA, USA, 2000, pp. 141–154.
  ista: 'De Alfaro L, Henzinger TA. 2000. Concurrent omega-regular games. Proceedings
    of the 15th Annual IEEE Symposium on Logic in Computer Science. LICS: Logic in
    Computer Science, 141–154.'
  mla: De Alfaro, Luca, and Thomas A. Henzinger. “Concurrent Omega-Regular Games.”
    <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i>,
    IEEE, 2000, pp. 141–54, doi:<a href="https://doi.org/10.1109/LICS.2000.855763">10.1109/LICS.2000.855763</a>.
  short: L. De Alfaro, T.A. Henzinger, in:, Proceedings of the 15th Annual IEEE Symposium
    on Logic in Computer Science, IEEE, 2000, pp. 141–154.
conference:
  end_date: 2000-06-28
  location: Santa Barbara, CA, USA
  name: 'LICS: Logic in Computer Science'
  start_date: 2000-06-26
date_created: 2018-12-11T12:09:50Z
date_published: 2000-01-01T00:00:00Z
date_updated: 2023-04-13T13:24:29Z
day: '01'
doi: 10.1109/LICS.2000.855763
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 141 - 154
publication: Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science
publication_identifier:
  isbn:
  - '0769507255'
publication_status: published
publisher: IEEE
publist_id: '82'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Concurrent omega-regular games
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2000'
...