[{"year":"2011","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and F. Horn, “The complexity of request-response games,” presented at the LATA: Language and Automata Theory and Applications, Tarragona, Spain, 2011, vol. 6638, pp. 227–237.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. “The Complexity of Request-Response Games.” edited by Adrian-Horia Dediu, Shunsuke Inenaga, and Carlos Martín-Vide, 6638:227–37. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-21254-3_17\">https://doi.org/10.1007/978-3-642-21254-3_17</a>.","ama":"Chatterjee K, Henzinger TA, Horn F. The complexity of request-response games. In: Dediu A-H, Inenaga S, Martín-Vide C, eds. Vol 6638. Springer; 2011:227-237. doi:<a href=\"https://doi.org/10.1007/978-3-642-21254-3_17\">10.1007/978-3-642-21254-3_17</a>","apa":"Chatterjee, K., Henzinger, T. A., &#38; Horn, F. (2011). The complexity of request-response games. In A.-H. Dediu, S. Inenaga, &#38; C. Martín-Vide (Eds.) (Vol. 6638, pp. 227–237). Presented at the LATA: Language and Automata Theory and Applications, Tarragona, Spain: Springer. <a href=\"https://doi.org/10.1007/978-3-642-21254-3_17\">https://doi.org/10.1007/978-3-642-21254-3_17</a>","ista":"Chatterjee K, Henzinger TA, Horn F. 2011. The complexity of request-response games. LATA: Language and Automata Theory and Applications, LNCS, vol. 6638, 227–237.","short":"K. Chatterjee, T.A. Henzinger, F. Horn, in:, A.-H. Dediu, S. Inenaga, C. Martín-Vide (Eds.), Springer, 2011, pp. 227–237.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Request-Response Games</i>. Edited by Adrian-Horia Dediu et al., vol. 6638, Springer, 2011, pp. 227–37, doi:<a href=\"https://doi.org/10.1007/978-3-642-21254-3_17\">10.1007/978-3-642-21254-3_17</a>."},"date_updated":"2021-01-12T07:42:54Z","type":"conference","date_published":"2011-01-01T00:00:00Z","day":"01","doi":"10.1007/978-3-642-21254-3_17","publist_id":"3258","abstract":[{"text":"We consider two-player graph games whose objectives are request-response condition, i.e conjunctions of conditions of the form \"if a state with property Rq is visited, then later a state with property Rp is visited\". The winner of such games can be decided in EXPTIME and the problem is known to be NP-hard. In this paper, we close this gap by showing that this problem is, in fact, EXPTIME-complete. We show that the problem becomes PSPACE-complete if we only consider games played on DAGs, and NP-complete or PTIME-complete if there is only one player (depending on whether he wants to enforce or spoil the request-response condition). We also present near-optimal bounds on the memory needed to design winning strategies for each player, in each case.","lang":"eng"}],"volume":6638,"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","status":"public","scopus_import":1,"_id":"3357","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"37327ACE-F248-11E8-B48F-1D18A9856A87","last_name":"Horn","first_name":"Florian","full_name":"Horn, Florian"}],"date_created":"2018-12-11T12:02:52Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication_status":"published","oa_version":"None","intvolume":"      6638","month":"01","title":"The complexity of request-response games","alternative_title":["LNCS"],"quality_controlled":"1","page":"227 - 237","language":[{"iso":"eng"}],"editor":[{"last_name":"Dediu","first_name":"Adrian-Horia","full_name":"Dediu, Adrian-Horia"},{"first_name":"Shunsuke","last_name":"Inenaga","full_name":"Inenaga, Shunsuke"},{"full_name":"Martín-Vide, Carlos","last_name":"Martín-Vide","first_name":"Carlos"}],"publisher":"Springer","conference":{"location":"Tarragona, Spain","end_date":"2011-05-31","start_date":"2011-05-26","name":"LATA: Language and Automata Theory and Applications"}},{"publisher":"Open Publishing Association","page":"30 - 39","quality_controlled":"1","publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T11:46:45Z","title":"How do we remember the past in randomised strategies? ","alternative_title":["EPTCS"],"intvolume":"        25","_id":"489","scopus_import":1,"author":[{"last_name":"Cristau","first_name":"Julien","full_name":"Cristau, Julien"},{"full_name":"David, Claire","first_name":"Claire","last_name":"David"},{"full_name":"Horn, Florian","last_name":"Horn","first_name":"Florian","id":"37327ACE-F248-11E8-B48F-1D18A9856A87"}],"volume":25,"doi":"10.4204/EPTCS.25.7","day":"09","abstract":[{"text":"Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.","lang":"eng"}],"date_updated":"2021-01-12T08:01:01Z","year":"2010","citation":{"ista":"Cristau J, David C, Horn F. 2010. How do we remember the past in randomised strategies? . Proceedings of GandALF 2010. GandALF: Games, Automata, Logic, and Formal Verification, EPTCS, vol. 25, 30–39.","mla":"Cristau, Julien, et al. “How Do We Remember the Past in Randomised Strategies? .” <i>Proceedings of GandALF 2010</i>, vol. 25, Open Publishing Association, 2010, pp. 30–39, doi:<a href=\"https://doi.org/10.4204/EPTCS.25.7\">10.4204/EPTCS.25.7</a>.","short":"J. Cristau, C. David, F. Horn, in:, Proceedings of GandALF 2010, Open Publishing Association, 2010, pp. 30–39.","chicago":"Cristau, Julien, Claire David, and Florian Horn. “How Do We Remember the Past in Randomised Strategies? .” In <i>Proceedings of GandALF 2010</i>, 25:30–39. Open Publishing Association, 2010. <a href=\"https://doi.org/10.4204/EPTCS.25.7\">https://doi.org/10.4204/EPTCS.25.7</a>.","ieee":"J. Cristau, C. David, and F. Horn, “How do we remember the past in randomised strategies? ,” in <i>Proceedings of GandALF 2010</i>, Minori, Amalfi Coast, Italy, 2010, vol. 25, pp. 30–39.","ama":"Cristau J, David C, Horn F. How do we remember the past in randomised strategies? . In: <i>Proceedings of GandALF 2010</i>. Vol 25. Open Publishing Association; 2010:30-39. doi:<a href=\"https://doi.org/10.4204/EPTCS.25.7\">10.4204/EPTCS.25.7</a>","apa":"Cristau, J., David, C., &#38; Horn, F. (2010). How do we remember the past in randomised strategies? . In <i>Proceedings of GandALF 2010</i> (Vol. 25, pp. 30–39). Minori, Amalfi Coast, Italy: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.25.7\">https://doi.org/10.4204/EPTCS.25.7</a>"},"conference":{"name":"GandALF: Games, Automata, Logic, and Formal Verification","start_date":"2010-06-17","location":"Minori, Amalfi Coast, Italy","end_date":"2010-06-18"},"language":[{"iso":"eng"}],"oa_version":"Published Version","month":"06","publication":"Proceedings of GandALF 2010","main_file_link":[{"url":"https://arxiv.org/abs/1006.1404v1","open_access":"1"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","oa":1,"publist_id":"7332","date_published":"2010-06-09T00:00:00Z","type":"conference"},{"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Obliging Games</i>. Vol. 6269, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 284–96, doi:<a href=\"https://doi.org/10.1007/978-3-642-15375-4_20\">10.1007/978-3-642-15375-4_20</a>.","short":"K. Chatterjee, F. Horn, C. Löding, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 284–296.","ista":"Chatterjee K, Horn F, Löding C. 2010. Obliging games. CONCUR: Concurrency Theory, LNCS, vol. 6269, 284–296.","apa":"Chatterjee, K., Horn, F., &#38; Löding, C. (2010). Obliging games (Vol. 6269, pp. 284–296). Presented at the CONCUR: Concurrency Theory, Paris, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.1007/978-3-642-15375-4_20\">https://doi.org/10.1007/978-3-642-15375-4_20</a>","ama":"Chatterjee K, Horn F, Löding C. Obliging games. In: Vol 6269. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:284-296. doi:<a href=\"https://doi.org/10.1007/978-3-642-15375-4_20\">10.1007/978-3-642-15375-4_20</a>","ieee":"K. Chatterjee, F. Horn, and C. Löding, “Obliging games,” presented at the CONCUR: Concurrency Theory, Paris, France, 2010, vol. 6269, pp. 284–296.","chicago":"Chatterjee, Krishnendu, Florian Horn, and Christof Löding. “Obliging Games,” 6269:284–96. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. <a href=\"https://doi.org/10.1007/978-3-642-15375-4_20\">https://doi.org/10.1007/978-3-642-15375-4_20</a>."},"year":"2010","date_updated":"2021-01-12T07:52:41Z","type":"conference","date_published":"2010-09-08T00:00:00Z","day":"08","doi":"10.1007/978-3-642-15375-4_20","publist_id":"2327","abstract":[{"lang":"eng","text":"Graph games of infinite length provide a natural model for open reactive systems: one player (Eve) represents the controller and the other player (Adam) represents the environment. The evolution of the system depends on the decisions of both players. The specification for the system is usually given as an ω-regular language L over paths and Eve’s goal is to ensure that the play belongs to L irrespective of Adam’s behaviour. The classical notion of winning strategies fails to capture several interesting scenarios. For example, strong fairness (Streett) conditions are specified by a number of request-grant pairs and require every pair that is requested infinitely often to be granted infinitely often: Eve might win just by preventing Adam from making any new request, but a “better” strategy would allow Adam to make as many requests as possible and still ensure fairness. To address such questions, we introduce the notion of obliging games, where Eve has to ensure a strong condition Φ, while always allowing Adam to satisfy a weak condition Ψ. We present a linear time reduction of obliging games with two Muller conditions Φ and Ψ to classical Muller games. We consider obliging Streett games and show they are co-NP complete, and show a natural quantitative optimisation problem for obliging Streett games is in FNP. We also show how obliging games can provide new and interesting semantics for multi-player games."}],"volume":6269,"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","status":"public","scopus_import":1,"_id":"3854","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Horn","first_name":"Florian","full_name":"Horn, Florian","id":"37327ACE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Löding, Christof","last_name":"Löding","first_name":"Christof"}],"department":[{"_id":"KrCh"}],"date_created":"2018-12-11T12:05:32Z","oa_version":"None","publication_status":"published","intvolume":"      6269","alternative_title":["LNCS"],"title":"Obliging games","month":"09","quality_controlled":"1","page":"284 - 296","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","conference":{"end_date":"2010-09-03","location":"Paris, France","name":"CONCUR: Concurrency Theory","start_date":"2010-08-31"}},{"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["004"],"file":[{"file_size":238091,"checksum":"1c50a9723fbae1b2c46d18138968efb3","date_created":"2018-12-12T11:53:50Z","file_name":"IST-2009-0002_IST-2009-0002.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:43Z","access_level":"open_access","relation":"main_file","creator":"system","file_id":"5511"}],"date_published":"2009-09-09T00:00:00Z","type":"technical_report","date_updated":"2020-07-14T23:07:47Z","year":"2009","citation":{"ista":"Chatterjee K, Henzinger TA, Horn F. 2009. Improved lower bounds for request-response and finitary Streett games, IST Austria, 11p.","short":"K. Chatterjee, T.A. Henzinger, F. Horn, Improved Lower Bounds for Request-Response and Finitary Streett Games, IST Austria, 2009.","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>.","ieee":"K. Chatterjee, T. A. Henzinger, and F. Horn, <i>Improved lower bounds for request-response and finitary Streett games</i>. IST Austria, 2009.","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>.","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>","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>"},"abstract":[{"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.","lang":"eng"}],"oa":1,"doi":"10.15479/AT:IST-2009-0002","day":"09","publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:43Z","language":[{"iso":"eng"}],"page":"11","publisher":"IST Austria","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"37327ACE-F248-11E8-B48F-1D18A9856A87","full_name":"Horn, Florian","last_name":"Horn","first_name":"Florian"}],"_id":"5394","has_accepted_license":"1","pubrep_id":"30","title":"Improved lower bounds for request-response and finitary Streett games","month":"09","alternative_title":["IST Austria Technical Report"],"publication_status":"published","oa_version":"Published Version","date_created":"2018-12-12T11:39:05Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}]},{"language":[{"iso":"eng"}],"month":"10","article_number":"1","oa_version":"Submitted Version","project":[{"grant_number":"215543","name":"COMponent-Based Embedded Systems design Techniques","call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"}],"publication":"ACM Transactions on Computational Logic (TOCL)","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"file_id":"5125","creator":"system","access_level":"open_access","relation":"main_file","date_updated":"2020-07-14T12:46:20Z","file_name":"IST-2012-53-v1+1_Finitary_winning_in_omega-regular_games.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:15:08Z","checksum":"139c4586d24f11e5da31fb3a0cf96ef4","file_size":180082}],"oa":1,"publist_id":"2309","date_published":"2009-10-01T00:00:00Z","type":"journal_article","publisher":"ACM","file_date_updated":"2020-07-14T12:46:20Z","ec_funded":1,"quality_controlled":"1","pubrep_id":"53","title":"Finitary winning in omega-regular games","intvolume":"        11","publication_status":"published","date_created":"2018-12-11T12:05:37Z","department":[{"_id":"KrCh"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"37327ACE-F248-11E8-B48F-1D18A9856A87","first_name":"Florian","last_name":"Horn","full_name":"Horn, Florian"}],"issue":"1","_id":"3870","scopus_import":1,"ddc":["004"],"volume":11,"acknowledgement":"This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, the NSF grants CCR-0132780, CNS-0720884, and CCR- 225610, by the Swiss National Science Foundation, by the COMBEST project of the European Union, and EU-TMR network Games.\r\nWe thank anonymous reviewers for useful comments.","abstract":[{"text":"Games on graphs with omega-regular objectives provide a model for the control and synthesis of reactive systems. Every omega-regular objective can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens “eventually.” Two main strengths of the classical, infinite-limit formulation of liveness are robustness (independence from the granularity of transitions) and simplicity (abstraction of complicated time bounds). However, the classical liveness formulation suffers from the drawback that the time until something good happens may be unbounded. A stronger formulation of liveness, so-called finitary liveness, overcomes this drawback, while still retaining robustness and simplicity. Finitary liveness requires that there exists an unknown, fixed bound b such that something good happens within b transitions. While for one-shot liveness (reachability) objectives, classical and finitary liveness coincide, for repeated liveness (Buchi) objectives, the finitary formulation is strictly stronger. In this work we study games with finitary parity and Streett objectives. We prove the determinacy of these games, present algorithms for solving these games, and characterize the memory requirements of winning strategies. We show that finitary parity games can be solved in polynomial time, which is not known for infinitary parity games. For finitary Streett games, we give an EXPTIME algorithm and show that the problem is NP-hard. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound.","lang":"eng"}],"doi":"10.1145/1614431.1614432","day":"01","date_updated":"2021-01-12T07:52:50Z","year":"2009","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and F. Horn, “Finitary winning in omega-regular games,” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 11, no. 1. ACM, 2009.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. “Finitary Winning in Omega-Regular Games.” <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM, 2009. <a href=\"https://doi.org/10.1145/1614431.1614432\">https://doi.org/10.1145/1614431.1614432</a>.","ama":"Chatterjee K, Henzinger TA, Horn F. Finitary winning in omega-regular games. <i>ACM Transactions on Computational Logic (TOCL)</i>. 2009;11(1). doi:<a href=\"https://doi.org/10.1145/1614431.1614432\">10.1145/1614431.1614432</a>","apa":"Chatterjee, K., Henzinger, T. A., &#38; Horn, F. (2009). Finitary winning in omega-regular games. <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM. <a href=\"https://doi.org/10.1145/1614431.1614432\">https://doi.org/10.1145/1614431.1614432</a>","ista":"Chatterjee K, Henzinger TA, Horn F. 2009. Finitary winning in omega-regular games. ACM Transactions on Computational Logic (TOCL). 11(1), 1.","short":"K. Chatterjee, T.A. Henzinger, F. Horn, ACM Transactions on Computational Logic (TOCL) 11 (2009).","mla":"Chatterjee, Krishnendu, et al. “Finitary Winning in Omega-Regular Games.” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 11, no. 1, 1, ACM, 2009, doi:<a href=\"https://doi.org/10.1145/1614431.1614432\">10.1145/1614431.1614432</a>."}},{"citation":{"short":"K. Chatterjee, T.A. Henzinger, F. Horn, in:, Springer, 2009, pp. 34–54.","mla":"Chatterjee, Krishnendu, et al. <i>Stochastic Games with Finitary Objectives</i>. Vol. 5734, Springer, 2009, pp. 34–54, doi:<a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">10.1007/978-3-642-03816-7_4</a>.","ista":"Chatterjee K, Henzinger TA, Horn F. 2009. Stochastic games with finitary objectives. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 5734, 34–54.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Horn, F. (2009). Stochastic games with finitary objectives (Vol. 5734, pp. 34–54). Presented at the MFCS: Mathematical Foundations of Computer Science, High Tatras, Slovakia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">https://doi.org/10.1007/978-3-642-03816-7_4</a>","ama":"Chatterjee K, Henzinger TA, Horn F. Stochastic games with finitary objectives. In: Vol 5734. Springer; 2009:34-54. doi:<a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">10.1007/978-3-642-03816-7_4</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. “Stochastic Games with Finitary Objectives,” 5734:34–54. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">https://doi.org/10.1007/978-3-642-03816-7_4</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and F. Horn, “Stochastic games with finitary objectives,” presented at the MFCS: Mathematical Foundations of Computer Science, High Tatras, Slovakia, 2009, vol. 5734, pp. 34–54."},"year":"2009","date_updated":"2021-01-12T07:59:35Z","abstract":[{"lang":"eng","text":"The synthesis of a reactive system with respect to all omega-regular specification requires the solution of a graph game. Such games have been extended in two natural ways. First, a game graph can be equipped with probabilistic choices between alternative transitions, thus allowing the, modeling of uncertain behaviour. These are called stochastic games. Second, a liveness specification can he strengthened to require satisfaction within all unknown but bounded amount of time. These are called finitary objectives. We study. for the first time, the, combination of Stochastic games and finitary objectives. We characterize the requirements on optimal strategies and provide algorithms for Computing the maximal achievable probability of winning stochastic games with finitary parity or Street, objectives. Most notably the set of state's from which a player can win with probability . for a finitary parity objective can he computed in polynomial time even though no polynomial-time algorithm is known in the nonfinitary case."}],"day":"01","doi":"10.1007/978-3-642-03816-7_4","acknowledgement":"This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), and by the European project Combest.","volume":5734,"author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger"},{"id":"37327ACE-F248-11E8-B48F-1D18A9856A87","last_name":"Horn","first_name":"Florian","full_name":"Horn, Florian"}],"scopus_import":1,"_id":"4543","intvolume":"      5734","alternative_title":["LNCS"],"title":"Stochastic games with finitary objectives","date_created":"2018-12-11T12:09:24Z","department":[{"_id":"KrCh"}],"publication_status":"published","quality_controlled":"1","ec_funded":1,"page":"34 - 54","publisher":"Springer","type":"conference","date_published":"2009-08-01T00:00:00Z","publist_id":"178","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","month":"08","project":[{"_id":"25EFB36C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"215543","name":"COMponent-Based Embedded Systems design Techniques"},{"_id":"25F1337C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Design for Embedded Systems","grant_number":"214373"}],"oa_version":"None","language":[{"iso":"eng"}],"conference":{"end_date":"2009-08-28","location":"High Tatras, Slovakia","name":"MFCS: Mathematical Foundations of Computer Science","start_date":"2009-08-24"}}]