---
_id: '5394'
abstract:
- lang: eng
  text: We consider two-player games played on graphs with request-response and finitary
    Streett objectives. We show these games are PSPACE-hard, improving the previous
    known NP-hardness. We also improve the lower bounds on memory required by the
    winning strategies for the players.
alternative_title:
- IST Austria Technical Report
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
- first_name: Florian
  full_name: Horn, Florian
  id: 37327ACE-F248-11E8-B48F-1D18A9856A87
  last_name: Horn
citation:
  ama: Chatterjee K, Henzinger TA, Horn F. <i>Improved Lower Bounds for Request-Response
    and Finitary Streett Games</i>. IST Austria; 2009. doi:<a href="https://doi.org/10.15479/AT:IST-2009-0002">10.15479/AT:IST-2009-0002</a>
  apa: Chatterjee, K., Henzinger, T. A., &#38; Horn, F. (2009). <i>Improved lower
    bounds for request-response and finitary Streett games</i>. IST Austria. <a href="https://doi.org/10.15479/AT:IST-2009-0002">https://doi.org/10.15479/AT:IST-2009-0002</a>
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. <i>Improved
    Lower Bounds for Request-Response and Finitary Streett Games</i>. IST Austria,
    2009. <a href="https://doi.org/10.15479/AT:IST-2009-0002">https://doi.org/10.15479/AT:IST-2009-0002</a>.
  ieee: K. Chatterjee, T. A. Henzinger, and F. Horn, <i>Improved lower bounds for
    request-response and finitary Streett games</i>. IST Austria, 2009.
  ista: Chatterjee K, Henzinger TA, Horn F. 2009. Improved lower bounds for request-response
    and finitary Streett games, IST Austria, 11p.
  mla: Chatterjee, Krishnendu, et al. <i>Improved Lower Bounds for Request-Response
    and Finitary Streett Games</i>. IST Austria, 2009, doi:<a href="https://doi.org/10.15479/AT:IST-2009-0002">10.15479/AT:IST-2009-0002</a>.
  short: K. Chatterjee, T.A. Henzinger, F. Horn, Improved Lower Bounds for Request-Response
    and Finitary Streett Games, IST Austria, 2009.
corr_author: '1'
date_created: 2018-12-12T11:39:05Z
date_published: 2009-09-09T00:00:00Z
date_updated: 2024-10-09T21:08:23Z
day: '09'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2009-0002
file:
- access_level: open_access
  checksum: 1c50a9723fbae1b2c46d18138968efb3
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:53:50Z
  date_updated: 2020-07-14T12:46:43Z
  file_id: '5511'
  file_name: IST-2009-0002_IST-2009-0002.pdf
  file_size: 238091
  relation: main_file
file_date_updated: 2020-07-14T12:46:43Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '11'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '30'
status: public
title: Improved lower bounds for request-response and finitary Streett games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2009'
...