Improved lower bounds for request-response and finitary Streett games
Chatterjee K, Henzinger TA, Horn F. 2009. Improved lower bounds for request-response and finitary Streett games, IST Austria, 11p.
Download
Technical Report
| Published
| English
Department
Series Title
IST Austria Technical Report
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.
Publishing Year
Date Published
2009-09-09
Publisher
IST Austria
Page
11
ISSN
IST-REx-ID
Cite this
Chatterjee K, Henzinger TA, Horn F. Improved Lower Bounds for Request-Response and Finitary Streett Games. IST Austria; 2009. doi:10.15479/AT:IST-2009-0002
Chatterjee, K., Henzinger, T. A., & Horn, F. (2009). Improved lower bounds for request-response and finitary Streett games. IST Austria. https://doi.org/10.15479/AT:IST-2009-0002
Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. Improved Lower Bounds for Request-Response and Finitary Streett Games. IST Austria, 2009. https://doi.org/10.15479/AT:IST-2009-0002.
K. Chatterjee, T. A. Henzinger, and F. Horn, Improved lower bounds for request-response and finitary Streett games. IST Austria, 2009.
Chatterjee K, Henzinger TA, Horn F. 2009. Improved lower bounds for request-response and finitary Streett games, IST Austria, 11p.
Chatterjee, Krishnendu, et al. Improved Lower Bounds for Request-Response and Finitary Streett Games. IST Austria, 2009, doi:10.15479/AT:IST-2009-0002.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
IST-2009-0002_IST-2009-0002.pdf
238.09 KB
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
1c50a9723fbae1b2c46d18138968efb3
Google Scholar