Improved lower bounds for request-response and finitary Streett games

K. Chatterjee, T.A. Henzinger, F. Horn, Improved Lower Bounds for Request-Response and Finitary Streett Games, IST Austria, 2009.

Download
OA 238.09 KB

Technical Report | Published | English
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
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.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:53:50Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar