--- res: bibo_abstract: - 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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Krishnendu foaf_name: Chatterjee, Krishnendu foaf_surname: Chatterjee foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-4561-241X - foaf_Person: foaf_givenName: Thomas A foaf_name: Henzinger, Thomas A foaf_surname: Henzinger foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87 orcid: 0000−0002−2985−7724 - foaf_Person: foaf_givenName: Florian foaf_name: Horn, Florian foaf_surname: Horn foaf_workInfoHomepage: http://www.librecat.org/personId=37327ACE-F248-11E8-B48F-1D18A9856A87 bibo_doi: 10.15479/AT:IST-2009-0002 dct_date: 2009^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/2664-1690 dct_language: eng dct_publisher: IST Austria@ dct_title: Improved lower bounds for request-response and finitary Streett games@ ...