thesis published Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Thomas A Henzinger author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724 Florian Horn author 37327ACE-F248-11E8-B48F-1D18A9856A87 KrCh department ToHe department 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. https://research-explorer.ista.ac.at/download/5394/5511/IST-2009-0002_IST-2009-0002.pdf application/pdfno IST Austria2009 eng 2664-169010.15479/AT:IST-2009-0002 11 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> Chatterjee K, Henzinger TA, Horn F. 2009. Improved lower bounds for request-response and finitary Streett games, IST Austria, 11p. 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>. 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>. K. Chatterjee, T. A. Henzinger, and F. Horn, <i>Improved lower bounds for request-response and finitary Streett games</i>. IST Austria, 2009. 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> K. Chatterjee, T.A. Henzinger, F. Horn, Improved Lower Bounds for Request-Response and Finitary Streett Games, IST Austria, 2009. 53942018-12-12T11:39:05Z2024-10-09T21:08:23Z