---
OA_type: closed access
_id: '4437'
abstract:
- lang: eng
  text: The synthesis of reactive systems requires the solution of two-player games
    on graphs with ω-regular objectives. When the objective is specified by a linear
    temporal logic formula or nondeterministic Büchi automaton, then previous algorithms
    for solving the game require the construction of an equivalent deterministic automaton.
    However, determinization for automata on infinite words is extremely complicated,
    and current implementations fail to produce deterministic automata even for relatively
    small inputs. We show how to construct, from a given nondeterministic Büchi automaton,
    an equivalent nondeterministic parity automaton that is good for solving games
    with objective . The main insight is that a nondeterministic automaton is good
    for solving games if it fairly simulates the equivalent deterministic automaton.
    In this way, we omit the determinization step in game solving and reactive synthesis.
    The fact that our automata are nondeterministic makes them surprisingly simple,
    amenable to symbolic implementation, and allows an incremental search for winning
    strategies.
acknowledgement: This research was supported in part by the Swiss National Science
  Foundation.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Nir
  full_name: Piterman, Nir
  last_name: Piterman
citation:
  ama: 'Henzinger TA, Piterman N. Solving games without determinization. In: <i>Proceedings
    of the 20th International Conference on Computer Science Logic</i>. Vol 4207.
    Springer; 2006:395-410. doi:<a href="https://doi.org/10.1007/11874683_26">10.1007/11874683_26</a>'
  apa: 'Henzinger, T. A., &#38; Piterman, N. (2006). Solving games without determinization.
    In <i>Proceedings of the 20th international conference on Computer Science Logic</i>
    (Vol. 4207, pp. 395–410). Szeged, Hungary: Springer. <a href="https://doi.org/10.1007/11874683_26">https://doi.org/10.1007/11874683_26</a>'
  chicago: Henzinger, Thomas A, and Nir Piterman. “Solving Games without Determinization.”
    In <i>Proceedings of the 20th International Conference on Computer Science Logic</i>,
    4207:395–410. Springer, 2006. <a href="https://doi.org/10.1007/11874683_26">https://doi.org/10.1007/11874683_26</a>.
  ieee: T. A. Henzinger and N. Piterman, “Solving games without determinization,”
    in <i>Proceedings of the 20th international conference on Computer Science Logic</i>,
    Szeged, Hungary, 2006, vol. 4207, pp. 395–410.
  ista: 'Henzinger TA, Piterman N. 2006. Solving games without determinization. Proceedings
    of the 20th international conference on Computer Science Logic. CSL: Computer
    Science Logic, LNCS, vol. 4207, 395–410.'
  mla: Henzinger, Thomas A., and Nir Piterman. “Solving Games without Determinization.”
    <i>Proceedings of the 20th International Conference on Computer Science Logic</i>,
    vol. 4207, Springer, 2006, pp. 395–410, doi:<a href="https://doi.org/10.1007/11874683_26">10.1007/11874683_26</a>.
  short: T.A. Henzinger, N. Piterman, in:, Proceedings of the 20th International Conference
    on Computer Science Logic, Springer, 2006, pp. 395–410.
conference:
  end_date: 2006-09-29
  location: Szeged, Hungary
  name: 'CSL: Computer Science Logic'
  start_date: 2006-09-25
date_created: 2018-12-11T12:08:51Z
date_published: 2006-09-20T00:00:00Z
date_updated: 2026-08-21T11:30:47Z
day: '20'
doi: 10.1007/11874683_26
extern: '1'
intvolume: '      4207'
language:
- iso: eng
month: '09'
oa_version: None
page: 395 - 410
publication: Proceedings of the 20th international conference on Computer Science
  Logic
publication_identifier:
  eisbn:
  - '9783540454595'
  eissn:
  - 1611-3349
  isbn:
  - '9783540454588'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
publist_id: '295'
status: public
title: Solving games without determinization
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4207
year: '2006'
...
---
OA_type: closed access
_id: '3891'
abstract:
- lang: eng
  text: 'We study infinite stochastic games played by two-players over a finite state
    space, with objectives specified by sets of infinite traces. The games are concurrent
    (players make moves simultaneously and independently), stochastic (the next state
    is determined by a probability distribution that depends on the current state
    and chosen moves of the players) and infinite (proceeds for infinite number of
    rounds). The analysis of concurrent stochastic games can be classified into: quantitative
    analysis, analyzing the optimum value of the game; and qualitative analysis, analyzing
    the set of states with optimum value 1. We consider concurrent games with tail
    objectives, i.e., objectives that are independent of the finite-prefix of traces,
    and show that the class of tail objectives are strictly richer than the omega-regular
    objectives. We develop new proof techniques to extend several properties of concurrent
    games with omega-regular objectives to concurrent games with tail objectives.
    We prove the positive limit-one property for tail objectives, that states for
    all concurrent games if the optimum value for a player is positive for a tail
    objective Phi at some state, then there is a state where the optimum value is
    1 for Phi, for the player. We also show that the optimum values of zero-sum (strictly
    conflicting objectives) games with tail objectives can be related to equilibrium
    values of nonzero-sum (not strictly conflicting objectives) games with simpler
    reachability objectives. A consequence of our analysis presents a polynomial time
    reduction of the quantitative analysis of tail objectives to the qualitative analysis
    for the sub-class of one-player stochastic games (Markov decision processes).'
alternative_title:
- 'LNCS '
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
citation:
  ama: 'Chatterjee K. Concurrent games with tail objectives. In: <i>Proceedings of
    the 20th International Conference on Computer Science Logic</i>. Vol 4207. Springer
    Nature; 2006:256-270. doi:<a href="https://doi.org/10.1007/11874683_17">10.1007/11874683_17</a>'
  apa: 'Chatterjee, K. (2006). Concurrent games with tail objectives. In <i>Proceedings
    of the 20th international conference on Computer Science Logic</i> (Vol. 4207,
    pp. 256–270). Szeged, Hungary: Springer Nature. <a href="https://doi.org/10.1007/11874683_17">https://doi.org/10.1007/11874683_17</a>'
  chicago: Chatterjee, Krishnendu. “Concurrent Games with Tail Objectives.” In <i>Proceedings
    of the 20th International Conference on Computer Science Logic</i>, 4207:256–70.
    Springer Nature, 2006. <a href="https://doi.org/10.1007/11874683_17">https://doi.org/10.1007/11874683_17</a>.
  ieee: K. Chatterjee, “Concurrent games with tail objectives,” in <i>Proceedings
    of the 20th international conference on Computer Science Logic</i>, Szeged, Hungary,
    2006, vol. 4207, pp. 256–270.
  ista: 'Chatterjee K. 2006. Concurrent games with tail objectives. Proceedings of
    the 20th international conference on Computer Science Logic. CSL: Computer Science
    Logic, LNCS , vol. 4207, 256–270.'
  mla: Chatterjee, Krishnendu. “Concurrent Games with Tail Objectives.” <i>Proceedings
    of the 20th International Conference on Computer Science Logic</i>, vol. 4207,
    Springer Nature, 2006, pp. 256–70, doi:<a href="https://doi.org/10.1007/11874683_17">10.1007/11874683_17</a>.
  short: K. Chatterjee, in:, Proceedings of the 20th International Conference on Computer
    Science Logic, Springer Nature, 2006, pp. 256–270.
conference:
  end_date: 2006-09-29
  location: Szeged, Hungary
  name: 'CSL: Computer Science Logic'
  start_date: 2006-09-25
date_created: 2018-12-11T12:05:44Z
date_published: 2006-09-28T00:00:00Z
date_updated: 2026-08-27T07:36:31Z
day: '28'
doi: 10.1007/11874683_17
extern: '1'
intvolume: '      4207'
language:
- iso: eng
month: '09'
oa_version: None
page: 256 - 270
publication: Proceedings of the 20th international conference on Computer Science
  Logic
publication_identifier:
  eisbn:
  - '9783540454595'
  isbn:
  - '9783540454588'
publication_status: published
publisher: Springer Nature
publist_id: '2272'
status: public
title: Concurrent games with tail objectives
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4207
year: '2006'
...
---
OA_type: closed access
_id: '3889'
abstract:
- lang: eng
  text: We study observation-based strategies for two-player turn-based games on graphs
    with omega-regular objectives. An observation-based strategy relies on imperfect
    information about the history of a play, namely, on the past sequence of observations.
    Such games occur in the synthesis of a controller that does not see the private
    state of the plant. Our main results are twofold. First, we give a fixed-point
    algorithm for computing the set of states from which a player can win with a deterministic
    observation-based strategy for any omega-regular objective. The fixed point is
    computed in the lattice of antichains of state sets. This algorithm has the advantages
    of being directed by the objective and of avoiding an explicit subset construction
    on the game graph. Second, we give an algorithm for computing the set of states
    from which a player can win with probability 1 with a randomized observation-based
    strategy for a Buchi objective. This set is of interest because in the absence
    of perfect information, randomized strategies are more powerful than deterministic
    ones. We show that our algorithms are optimal by proving matching lower bounds.
acknowledgement: This research was supported in part by the NSF grants CCR-0225610
  and CCR-0234690, by the SNSF under the Indo-Swiss Joint Research Programme, and
  by the FRFC project “Centre Fédéré en Vérification” funded by the FNRS under grant
  2.4530.02.
alternative_title:
- LNCS
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: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Jean
  full_name: Raskin, Jean
  last_name: Raskin
citation:
  ama: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. Algorithms for omega-regular
    games with imperfect information. In: <i>Proceedings of the 20th International
    Conference on Computer Science Logic</i>. Vol 4207. Springer Nature; 2006:287-302.
    doi:<a href="https://doi.org/10.1007/11874683_19">10.1007/11874683_19</a>'
  apa: 'Chatterjee, K., Doyen, L., Henzinger, T. A., &#38; Raskin, J. (2006). Algorithms
    for omega-regular games with imperfect information. In <i>Proceedings of the 20th
    international conference on Computer Science Logic</i> (Vol. 4207, pp. 287–302).
    Szeged, Hungary: Springer Nature. <a href="https://doi.org/10.1007/11874683_19">https://doi.org/10.1007/11874683_19</a>'
  chicago: Chatterjee, Krishnendu, Laurent Doyen, Thomas A Henzinger, and Jean Raskin.
    “Algorithms for Omega-Regular Games with Imperfect Information.” In <i>Proceedings
    of the 20th International Conference on Computer Science Logic</i>, 4207:287–302.
    Springer Nature, 2006. <a href="https://doi.org/10.1007/11874683_19">https://doi.org/10.1007/11874683_19</a>.
  ieee: K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin, “Algorithms for omega-regular
    games with imperfect information,” in <i>Proceedings of the 20th international
    conference on Computer Science Logic</i>, Szeged, Hungary, 2006, vol. 4207, pp.
    287–302.
  ista: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. 2006. Algorithms for omega-regular
    games with imperfect information. Proceedings of the 20th international conference
    on Computer Science Logic. CSL: Computer Science Logic, LNCS, vol. 4207, 287–302.'
  mla: Chatterjee, Krishnendu, et al. “Algorithms for Omega-Regular Games with Imperfect
    Information.” <i>Proceedings of the 20th International Conference on Computer
    Science Logic</i>, vol. 4207, Springer Nature, 2006, pp. 287–302, doi:<a href="https://doi.org/10.1007/11874683_19">10.1007/11874683_19</a>.
  short: K. Chatterjee, L. Doyen, T.A. Henzinger, J. Raskin, in:, Proceedings of the
    20th International Conference on Computer Science Logic, Springer Nature, 2006,
    pp. 287–302.
conference:
  end_date: 2006-09-29
  location: Szeged, Hungary
  name: 'CSL: Computer Science Logic'
  start_date: 2006-09-25
date_created: 2018-12-11T12:05:43Z
date_published: 2006-11-13T00:00:00Z
date_updated: 2026-08-27T08:04:08Z
day: '13'
doi: 10.1007/11874683_19
extern: '1'
intvolume: '      4207'
language:
- iso: eng
month: '11'
oa_version: None
page: 287 - 302
publication: Proceedings of the 20th international conference on Computer Science
  Logic
publication_identifier:
  eisbn:
  - '9783540454595'
  eissn:
  - 1611-3349
  isbn:
  - '9783540454588'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2276'
status: public
title: Algorithms for omega-regular games with imperfect information
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4207
year: '2006'
...
---
OA_type: closed access
_id: '3499'
abstract:
- lang: eng
  text: 'We study infinite stochastic games played by n-players on a finite graph
    with goals specified by sets of infinite traces. The games are concurrent (each
    player simultaneously and independently chooses an action at each round), stochastic
    (the next state is determined by a probability distribution depending on the current
    state and the chosen actions), infinite (the game continues for an infinite number
    of rounds), nonzero-sum (the players’ goals are not necessarily conflicting),
    and undiscounted. We show that if each player has an upward-closed objective,
    then there exists an ε-Nash equilibrium in memoryless strategies, for every ε&gt;0;
    and exact Nash equilibria need not exist. Upward-closure of an objective means
    that if a set Z of infinitely repeating states is winning, then all supersets
    of Z of infinitely repeating states are also winning. Memoryless strategies are
    strategies that are independent of history of plays and depend only on the current
    state. We also study the complexity of finding values (payoff profile) of an ε-Nash
    equilibrium. We show that the values of an ε-Nash equilibrium in nonzero-sum concurrent
    games with upward-closed objectives for all players can be computed by computing
    ε-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives
    for all players and a polynomial procedure. As a consequence we establish that
    values of an ε-Nash equilibrium can be computed in TFNP (total functional NP),
    and hence in EXPTIME. '
acknowledgement: This research was supported in part by the NSF grants CCR-0225610
  and CCR- 0234690, and by the SNSF under the Indo-Swiss Joint Research Programme.
alternative_title:
- 'LNCS '
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
citation:
  ama: 'Chatterjee K. Nash equilibrium for upward-closed objectives. In: <i>Proceedings
    of the 20th International Conference on Computer Science Logic</i>. Vol 4207.
    Springer Nature; 2006:271-286. doi:<a href="https://doi.org/10.1007/11874683_18">10.1007/11874683_18</a>'
  apa: 'Chatterjee, K. (2006). Nash equilibrium for upward-closed objectives. In <i>Proceedings
    of the 20th international conference on Computer Science Logic</i> (Vol. 4207,
    pp. 271–286). Szeged, Hungary: Springer Nature. <a href="https://doi.org/10.1007/11874683_18">https://doi.org/10.1007/11874683_18</a>'
  chicago: Chatterjee, Krishnendu. “Nash Equilibrium for Upward-Closed Objectives.”
    In <i>Proceedings of the 20th International Conference on Computer Science Logic</i>,
    4207:271–86. Springer Nature, 2006. <a href="https://doi.org/10.1007/11874683_18">https://doi.org/10.1007/11874683_18</a>.
  ieee: K. Chatterjee, “Nash equilibrium for upward-closed objectives,” in <i>Proceedings
    of the 20th international conference on Computer Science Logic</i>, Szeged, Hungary,
    2006, vol. 4207, pp. 271–286.
  ista: 'Chatterjee K. 2006. Nash equilibrium for upward-closed objectives. Proceedings
    of the 20th international conference on Computer Science Logic. CSL: Computer
    Science Logic, LNCS , vol. 4207, 271–286.'
  mla: Chatterjee, Krishnendu. “Nash Equilibrium for Upward-Closed Objectives.” <i>Proceedings
    of the 20th International Conference on Computer Science Logic</i>, vol. 4207,
    Springer Nature, 2006, pp. 271–86, doi:<a href="https://doi.org/10.1007/11874683_18">10.1007/11874683_18</a>.
  short: K. Chatterjee, in:, Proceedings of the 20th International Conference on Computer
    Science Logic, Springer Nature, 2006, pp. 271–286.
conference:
  end_date: 2006-09-29
  location: Szeged, Hungary
  name: 'CSL: Computer Science Logic'
  start_date: 2006-09-25
date_created: 2018-12-11T12:03:39Z
date_published: 2006-09-28T00:00:00Z
date_updated: 2026-08-28T11:22:40Z
day: '28'
doi: 10.1007/11874683_18
extern: '1'
intvolume: '      4207'
language:
- iso: eng
month: '09'
oa_version: None
page: 271 - 286
publication: Proceedings of the 20th international conference on Computer Science
  Logic
publication_identifier:
  eisbn:
  - '9783540454595'
  eissn:
  - 1611-3349
  isbn:
  - '9783540454588'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2888'
status: public
title: Nash equilibrium for upward-closed objectives
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4207
year: '2006'
...