---
OA_type: closed access
_id: '4539'
abstract:
- lang: eng
  text: Games on graphs with ω-regular objectives provide a model for the control
    and synthesis of reactive systems. Every ω-regular objective can be decomposed
    into a safety part and a liveness part. The liveness part ensures that something
    good happens “eventually.” Two main strengths of the classical, infinite-limit
    formulation of liveness are robustness (independence from the granularity of transitions)
    and simplicity (abstraction of complicated time bounds). However, the classical
    liveness formulation suffers from the drawback that the time until something good
    happens may be unbounded. A stronger formulation of liveness, so-called finitary
    liveness, overcomes this drawback, while still retaining robustness and simplicity.
    Finitary liveness requires that there exists an unknown, fixed bound b such that
    something good happens within b transitions. While for one-shot liveness (reachability)
    objectives, classical and finitary liveness coincide, for repeated liveness (Büchi)
    objectives, the finitary formulation is strictly stronger. In this work we study
    games with finitary parity and Streett (fairness) objectives. We prove the determinacy
    of these games, present algorithms for solving these games, and characterize the
    memory requirements of winning strategies. Our algorithms can be used, for example,
    for synthesizing controllers that do not let the response time of a system increase
    without bound.
acknowledgement: This research was supported in part by the AFOSR MURI grant F49620-00-1-0327
  and the NSF ITR grant CCR-0225610.
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: 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, Henzinger TA. Finitary winning in omega-regular games. In: <i>Proceedings
    of the 12th International Conference on Tools and Algorithms for the Construction
    and Analysis of Systems</i>. Vol 3920. Springer; 2006:257-271. doi:<a href="https://doi.org/10.1007/11691372_17">10.1007/11691372_17</a>'
  apa: 'Chatterjee, K., &#38; Henzinger, T. A. (2006). Finitary winning in omega-regular
    games. In <i>Proceedings of the 12th international conference on Tools and Algorithms
    for the Construction and Analysis of Systems</i> (Vol. 3920, pp. 257–271). Vienna,
    Austria: Springer. <a href="https://doi.org/10.1007/11691372_17">https://doi.org/10.1007/11691372_17</a>'
  chicago: Chatterjee, Krishnendu, and Thomas A Henzinger. “Finitary Winning in Omega-Regular
    Games.” In <i>Proceedings of the 12th International Conference on Tools and Algorithms
    for the Construction and Analysis of Systems</i>, 3920:257–71. Springer, 2006.
    <a href="https://doi.org/10.1007/11691372_17">https://doi.org/10.1007/11691372_17</a>.
  ieee: K. Chatterjee and T. A. Henzinger, “Finitary winning in omega-regular games,”
    in <i>Proceedings of the 12th international conference on Tools and Algorithms
    for the Construction and Analysis of Systems</i>, Vienna, Austria, 2006, vol.
    3920, pp. 257–271.
  ista: 'Chatterjee K, Henzinger TA. 2006. Finitary winning in omega-regular games.
    Proceedings of the 12th international conference on Tools and Algorithms for the
    Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction
    and Analysis of Systems, LNCS, vol. 3920, 257–271.'
  mla: Chatterjee, Krishnendu, and Thomas A. Henzinger. “Finitary Winning in Omega-Regular
    Games.” <i>Proceedings of the 12th International Conference on Tools and Algorithms
    for the Construction and Analysis of Systems</i>, vol. 3920, Springer, 2006, pp.
    257–71, doi:<a href="https://doi.org/10.1007/11691372_17">10.1007/11691372_17</a>.
  short: K. Chatterjee, T.A. Henzinger, in:, Proceedings of the 12th International
    Conference on Tools and Algorithms for the Construction and Analysis of Systems,
    Springer, 2006, pp. 257–271.
conference:
  end_date: 2006-04-02
  location: Vienna, Austria
  name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
  start_date: 2006-03-25
date_created: 2018-12-11T12:09:22Z
date_published: 2006-03-15T00:00:00Z
date_updated: 2026-08-21T10:38:21Z
day: '15'
doi: 10.1007/11691372_17
extern: '1'
fulldoi: https://doi.org/10.1007/11691372_17
intvolume: '      3920'
language:
- iso: eng
month: '03'
oa_version: None
page: 257 - 271
publication: Proceedings of the 12th international conference on Tools and Algorithms
  for the Construction and Analysis of Systems
publication_identifier:
  eisbn:
  - '9783540330578'
  isbn:
  - '9783540330561'
publication_status: published
publisher: Springer
publist_id: '183'
status: public
title: Finitary winning in omega-regular games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3920
year: '2006'
...