[{"publisher":"Springer","date_published":"2014-01-01T00:00:00Z","page":"110 - 121","department":[{"_id":"KrCh"}],"volume":8573,"quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"external_id":{"arxiv":["1404.5453"]},"abstract":[{"lang":"eng","text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable in general, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games."}],"publication_status":"published","doi":"10.1007/978-3-662-43951-7_10","_id":"2163","ec_funded":1,"related_material":{"record":[{"status":"public","id":"5418","relation":"earlier_version"}]},"acknowledgement":"This research was partly supported by European project Cassting (FP7-601148).\r\nTechnical Report under https://research-explorer.app.ist.ac.at/record/5418\r\n","year":"2014","date_created":"2018-12-11T11:56:04Z","publist_id":"4821","citation":{"apa":"Chatterjee, K., &#38; Doyen, L. (2014). Games with a weak adversary. In <i>Lecture Notes in Computer Science</i> (Vol. 8573, pp. 110–121). Copenhagen, Denmark: Springer. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">https://doi.org/10.1007/978-3-662-43951-7_10</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” <i>Lecture Notes in Computer Science</i>, vol. 8573, no. Part 2, Springer, 2014, pp. 110–21, doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">10.1007/978-3-662-43951-7_10</a>.","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573, 110–121.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” In <i>Lecture Notes in Computer Science</i>, 8573:110–21. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">https://doi.org/10.1007/978-3-662-43951-7_10</a>.","short":"K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121.","ama":"Chatterjee K, Doyen L. Games with a weak adversary. In: <i>Lecture Notes in Computer Science</i>. Vol 8573. Springer; 2014:110-121. doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">10.1007/978-3-662-43951-7_10</a>","ieee":"K. Chatterjee and L. Doyen, “Games with a weak adversary,” in <i>Lecture Notes in Computer Science</i>, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 110–121."},"alternative_title":["LNCS"],"status":"public","type":"conference","conference":{"start_date":"2014-07-08","name":"ICALP: Automata, Languages and Programming","end_date":"2014-07-11","location":"Copenhagen, Denmark"},"month":"01","main_file_link":[{"url":"https://arxiv.org/abs/1404.5453","open_access":"1"}],"day":"01","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"}],"arxiv":1,"publication":"Lecture Notes in Computer Science","language":[{"iso":"eng"}],"intvolume":"      8573","date_updated":"2023-02-23T12:25:29Z","oa":1,"issue":"Part 2","title":"Games with a weak adversary"},{"intvolume":"        51","scopus_import":1,"has_accepted_license":"1","oa":1,"date_updated":"2021-01-12T06:55:51Z","pubrep_id":"71","issue":"3-4","article_processing_charge":"No","title":"Synthesizing robust systems","publication":"Acta Informatica","language":[{"iso":"eng"}],"month":"06","oa_version":"Submitted Version","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_id":"5234","checksum":"d7f560f3d923f0f00aa10a0652f83273","file_name":"IST-2012-71-v1+1_Synthesizing_robust_systems.pdf","date_updated":"2020-07-14T12:45:31Z","date_created":"2018-12-12T10:16:44Z","creator":"system","relation":"main_file","access_level":"open_access","file_size":169523,"content_type":"application/pdf"}],"author":[{"full_name":"Bloem, Roderick","first_name":"Roderick","last_name":"Bloem"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"full_name":"Greimel, Karin","first_name":"Karin","last_name":"Greimel"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Hofferek","first_name":"Georg","full_name":"Hofferek, Georg"},{"last_name":"Jobstmann","first_name":"Barbara","full_name":"Jobstmann, Barbara"},{"last_name":"Könighofer","first_name":"Bettina","full_name":"Könighofer, Bettina"},{"first_name":"Robert","full_name":"Könighofer, Robert","last_name":"Könighofer"}],"status":"public","type":"journal_article","ec_funded":1,"year":"2014","citation":{"apa":"Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., Hofferek, G., Jobstmann, B., … Könighofer, R. (2014). Synthesizing robust systems. <i>Acta Informatica</i>. Springer. <a href=\"https://doi.org/10.1007/s00236-013-0191-5\">https://doi.org/10.1007/s00236-013-0191-5</a>","ista":"Bloem R, Chatterjee K, Greimel K, Henzinger TA, Hofferek G, Jobstmann B, Könighofer B, Könighofer R. 2014. Synthesizing robust systems. Acta Informatica. 51(3–4), 193–220.","mla":"Bloem, Roderick, et al. “Synthesizing Robust Systems.” <i>Acta Informatica</i>, vol. 51, no. 3–4, Springer, 2014, pp. 193–220, doi:<a href=\"https://doi.org/10.1007/s00236-013-0191-5\">10.1007/s00236-013-0191-5</a>.","chicago":"Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger, Georg Hofferek, Barbara Jobstmann, Bettina Könighofer, and Robert Könighofer. “Synthesizing Robust Systems.” <i>Acta Informatica</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00236-013-0191-5\">https://doi.org/10.1007/s00236-013-0191-5</a>.","short":"R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, G. Hofferek, B. Jobstmann, B. Könighofer, R. Könighofer, Acta Informatica 51 (2014) 193–220.","ama":"Bloem R, Chatterjee K, Greimel K, et al. Synthesizing robust systems. <i>Acta Informatica</i>. 2014;51(3-4):193-220. doi:<a href=\"https://doi.org/10.1007/s00236-013-0191-5\">10.1007/s00236-013-0191-5</a>","ieee":"R. Bloem <i>et al.</i>, “Synthesizing robust systems,” <i>Acta Informatica</i>, vol. 51, no. 3–4. Springer, pp. 193–220, 2014."},"date_created":"2018-12-11T11:56:13Z","publist_id":"4787","doi":"10.1007/s00236-013-0191-5","file_date_updated":"2020-07-14T12:45:31Z","article_type":"original","_id":"2187","ddc":["621"],"abstract":[{"lang":"eng","text":"Systems should not only be correct but also robust in the sense that they behave reasonably in unexpected situations. This article addresses synthesis of robust reactive systems from temporal specifications. Existing methods allow arbitrary behavior if assumptions in the specification are violated. To overcome this, we define two robustness notions, combine them, and show how to enforce them in synthesis. The first notion applies to safety properties: If safety assumptions are violated temporarily, we require that the system recovers to normal operation with as few errors as possible. The second notion requires that, if liveness assumptions are violated, as many guarantees as possible should be fulfilled nevertheless. We present a synthesis procedure achieving this for the important class of GR(1) specifications, and establish complexity bounds. We also present an implementation of a special case of robustness, and show experimental results."}],"publication_status":"published","publisher":"Springer","date_published":"2014-06-01T00:00:00Z","page":"193 - 220","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"volume":51,"quality_controlled":"1","project":[{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","call_identifier":"FWF","name":"Moderne Concurrency Paradigms"},{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","call_identifier":"FP7","name":"Quantitative Reactive Modeling"}]},{"publication_status":"published","abstract":[{"lang":"eng","text":"We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula φ. The automaton is the product of a master automaton and an array of slave automata, one for each G-subformula of φ. The slave automaton for G ψ is in charge of recognizing whether FG ψ holds. As opposed to standard determinization procedures, the states of all our automata have a clear logical structure, which allows for various optimizations. Our construction subsumes former algorithms for fragments of LTL. Experimental results show improvement in the sizes of the resulting automata compared to existing methods."}],"project":[{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","call_identifier":"FP7"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms","call_identifier":"FWF"}],"quality_controlled":"1","volume":8559,"page":"192 - 208","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"date_published":"2014-01-01T00:00:00Z","publisher":"Springer","date_created":"2018-12-11T11:56:14Z","citation":{"chicago":"Esparza, Javier, and Jan Kretinsky. “From LTL to Deterministic Automata: A Safraless Compositional Approach,” 8559:192–208. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">https://doi.org/10.1007/978-3-319-08867-9_13</a>.","mla":"Esparza, Javier, and Jan Kretinsky. <i>From LTL to Deterministic Automata: A Safraless Compositional Approach</i>. Vol. 8559, Springer, 2014, pp. 192–208, doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">10.1007/978-3-319-08867-9_13</a>.","ista":"Esparza J, Kretinsky J. 2014. From LTL to deterministic automata: A safraless compositional approach. CAV: Computer Aided Verification, LNCS, vol. 8559, 192–208.","short":"J. Esparza, J. Kretinsky, in:, Springer, 2014, pp. 192–208.","ieee":"J. Esparza and J. Kretinsky, “From LTL to deterministic automata: A safraless compositional approach,” presented at the CAV: Computer Aided Verification, 2014, vol. 8559, pp. 192–208.","ama":"Esparza J, Kretinsky J. From LTL to deterministic automata: A safraless compositional approach. In: Vol 8559. Springer; 2014:192-208. doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">10.1007/978-3-319-08867-9_13</a>","apa":"Esparza, J., &#38; Kretinsky, J. (2014). From LTL to deterministic automata: A safraless compositional approach (Vol. 8559, pp. 192–208). Presented at the CAV: Computer Aided Verification, Springer. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">https://doi.org/10.1007/978-3-319-08867-9_13</a>"},"publist_id":"4784","year":"2014","acknowledgement":"The author is on leave from Faculty of Informatics, Masaryk University, Czech Republic, and partially supported by the Czech Science Foundation, grant No. P202/12/G061.","ec_funded":1,"_id":"2190","doi":"10.1007/978-3-319-08867-9_13","author":[{"full_name":"Esparza, Javier","first_name":"Javier","last_name":"Esparza"},{"orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","first_name":"Jan","full_name":"Kretinsky, Jan"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","day":"01","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1402.3388"}],"month":"01","conference":{"name":"CAV: Computer Aided Verification"},"type":"conference","status":"public","alternative_title":["LNCS"],"title":"From LTL to deterministic automata: A safraless compositional approach","oa":1,"date_updated":"2021-01-12T06:55:53Z","intvolume":"      8559","language":[{"iso":"eng"}]},{"month":"04","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.2141"}],"day":"01","oa_version":"Preprint","arxiv":1,"author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}],"type":"journal_article","status":"public","intvolume":"        15","scopus_import":1,"issue":"2","date_updated":"2023-02-23T12:23:43Z","oa":1,"title":"Partial-observation stochastic games: How to win when belief fails","publication":"ACM Transactions on Computational Logic (TOCL)","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"In two-player finite-state stochastic games of partial observation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distribution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Our main results for pure strategies are as follows: (1) For one-sided games with player 2 having perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algorithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 having perfect observation we show that nonelementarymemory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least nonelementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibit serious flaws in previous results of the literature: we show a nonelementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed."}],"external_id":{"arxiv":["1107.2141"]},"publication_status":"published","date_published":"2014-04-01T00:00:00Z","publisher":"ACM","volume":15,"quality_controlled":"1","department":[{"_id":"KrCh"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1903"},{"status":"public","id":"2955","relation":"earlier_version"},{"status":"public","relation":"earlier_version","id":"5381"}]},"article_number":"16","year":"2014","publist_id":"4759","date_created":"2018-12-11T11:56:21Z","citation":{"short":"K. Chatterjee, L. Doyen, ACM Transactions on Computational Logic (TOCL) 15 (2014).","ama":"Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when belief fails. <i>ACM Transactions on Computational Logic (TOCL)</i>. 2014;15(2). doi:<a href=\"https://doi.org/10.1145/2579821\">10.1145/2579821</a>","ieee":"K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to win when belief fails,” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 15, no. 2. ACM, 2014.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 15, no. 2, 16, ACM, 2014, doi:<a href=\"https://doi.org/10.1145/2579821\">10.1145/2579821</a>.","ista":"Chatterjee K, Doyen L. 2014. Partial-observation stochastic games: How to win when belief fails. ACM Transactions on Computational Logic (TOCL). 15(2), 16.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM, 2014. <a href=\"https://doi.org/10.1145/2579821\">https://doi.org/10.1145/2579821</a>.","apa":"Chatterjee, K., &#38; Doyen, L. (2014). Partial-observation stochastic games: How to win when belief fails. <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM. <a href=\"https://doi.org/10.1145/2579821\">https://doi.org/10.1145/2579821</a>"},"doi":"10.1145/2579821","_id":"2211"},{"title":"Perfect-information stochastic mean-payoff parity games","date_updated":"2023-02-23T12:24:50Z","scopus_import":1,"intvolume":"      8412","language":[{"iso":"eng"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Laurent","full_name":"Doyen, Laurent","last_name":"Doyen"},{"first_name":"Hugo","full_name":"Gimbert, Hugo","last_name":"Gimbert"},{"last_name":"Oualhadj","first_name":"Youssouf","full_name":"Oualhadj, Youssouf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"None","month":"04","conference":{"name":"FoSSaCS: Foundations of Software Science and Computation Structures","start_date":"2014-04-05","location":"Grenoble, France","end_date":"2014-04-13"},"status":"public","type":"conference","alternative_title":["LNCS"],"publist_id":"4758","date_created":"2018-12-11T11:56:21Z","citation":{"apa":"Chatterjee, K., Doyen, L., Gimbert, H., &#38; Oualhadj, Y. (2014). Perfect-information stochastic mean-payoff parity games (Vol. 8412, pp. 210–225). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">https://doi.org/10.1007/978-3-642-54830-7_14</a>","mla":"Chatterjee, Krishnendu, et al. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. Vol. 8412, Springer, 2014, pp. 210–25, doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">10.1007/978-3-642-54830-7_14</a>.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. “Perfect-Information Stochastic Mean-Payoff Parity Games,” 8412:210–25. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">https://doi.org/10.1007/978-3-642-54830-7_14</a>.","ista":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2014. Perfect-information stochastic mean-payoff parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 210–225.","ama":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-information stochastic mean-payoff parity games. In: Vol 8412. Springer; 2014:210-225. doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">10.1007/978-3-642-54830-7_14</a>","ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, “Perfect-information stochastic mean-payoff parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 210–225.","short":"K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, in:, Springer, 2014, pp. 210–225."},"year":"2014","acknowledgement":"This research was supported by European project Cassting (FP7-601148).\r\nA Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/128.","related_material":{"record":[{"status":"public","id":"5405","relation":"earlier_version"}]},"ec_funded":1,"_id":"2212","doi":"10.1007/978-3-642-54830-7_14","publication_status":"published","abstract":[{"lang":"eng","text":"The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2 1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2 1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic). We present an algorithm running in time O(d·n2d·MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2 1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective). "}],"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"volume":8412,"quality_controlled":"1","page":"210 - 225","department":[{"_id":"KrCh"}],"date_published":"2014-04-01T00:00:00Z","publisher":"Springer"},{"doi":"10.1007/978-3-642-54830-7_16","_id":"2213","ec_funded":1,"related_material":{"record":[{"id":"5408","relation":"earlier_version","status":"public"}]},"acknowledgement":"This research was supported by European project Cassting (FP7-601148), NSF grants CNS 1049862 and CCF-1139011, by NSF Expe ditions in Computing project “ExCAPE: Expeditions in Computer Augmented Program Engineering”, by BSF grant 9800096, and by gift from Intel.","year":"2014","publist_id":"4757","citation":{"apa":"Chatterjee, K., Doyen, L., Nain, S., &#38; Vardi, M. (2014). The complexity of partial-observation stochastic parity games with finite-memory strategies (Vol. 8412, pp. 242–257). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">https://doi.org/10.1007/978-3-642-54830-7_16</a>","ieee":"K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, “The complexity of partial-observation stochastic parity games with finite-memory strategies,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 242–257.","ama":"Chatterjee K, Doyen L, Nain S, Vardi M. The complexity of partial-observation stochastic parity games with finite-memory strategies. In: Vol 8412. Springer; 2014:242-257. doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">10.1007/978-3-642-54830-7_16</a>","short":"K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies</i>. Vol. 8412, Springer, 2014, pp. 242–57, doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">10.1007/978-3-642-54830-7_16</a>.","ista":"Chatterjee K, Doyen L, Nain S, Vardi M. 2014. The complexity of partial-observation stochastic parity games with finite-memory strategies. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 242–257.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. “The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies,” 8412:242–57. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">https://doi.org/10.1007/978-3-642-54830-7_16</a>."},"date_created":"2018-12-11T11:56:21Z","publisher":"Springer","date_published":"2014-04-01T00:00:00Z","page":"242 - 257","department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":8412,"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1401.3289"]},"abstract":[{"text":"We consider two-player partial-observation stochastic games on finitestate graphs where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are ε-regular conditions specified as parity objectives. The qualitative-analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). These qualitative-analysis problems are known to be undecidable. However in many applications the relevant question is the existence of finite-memory strategies, and the qualitative-analysis problems under finite-memory strategies was recently shown to be decidable in 2EXPTIME.We improve the complexity and show that the qualitative-analysis problems for partial-observation stochastic parity games under finite-memory strategies are EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis.","lang":"eng"}],"publication_status":"published","language":[{"iso":"eng"}],"intvolume":"      8412","scopus_import":1,"date_updated":"2023-02-23T12:24:58Z","oa":1,"title":"The complexity of partial-observation stochastic parity games with finite-memory strategies","alternative_title":["LNCS"],"type":"conference","status":"public","conference":{"location":"Grenoble, France","end_date":"2014-04-13","name":"FoSSaCS: Foundations of Software Science and Computation Structures","start_date":"2014-04-05"},"month":"04","oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/1401.3289","open_access":"1"}],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Laurent","full_name":"Doyen, Laurent","last_name":"Doyen"},{"last_name":"Nain","first_name":"Sumit","full_name":"Nain, Sumit"},{"full_name":"Vardi, Moshe","first_name":"Moshe","last_name":"Vardi"}],"arxiv":1},{"_id":"2216","language":[{"iso":"eng"}],"doi":"10.1145/2562059.2562141","title":"Edit distance for timed automata","publist_id":"4752","date_created":"2018-12-11T11:56:22Z","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Majumdar, R. (2014). Edit distance for timed automata (pp. 303–312). Presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany: Springer. <a href=\"https://doi.org/10.1145/2562059.2562141\">https://doi.org/10.1145/2562059.2562141</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, “Edit distance for timed automata,” presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany, 2014, pp. 303–312.","ama":"Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit distance for timed automata. In: Springer; 2014:303-312. doi:<a href=\"https://doi.org/10.1145/2562059.2562141\">10.1145/2562059.2562141</a>","short":"K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, in:, Springer, 2014, pp. 303–312.","ista":"Chatterjee K, Ibsen-Jensen R, Majumdar R. 2014. Edit distance for timed automata. HSCC: Hybrid Systems - Computation and Control, 303–312.","mla":"Chatterjee, Krishnendu, et al. <i>Edit Distance for Timed Automata</i>. Springer, 2014, pp. 303–12, doi:<a href=\"https://doi.org/10.1145/2562059.2562141\">10.1145/2562059.2562141</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Ritankar Majumdar. “Edit Distance for Timed Automata,” 303–12. Springer, 2014. <a href=\"https://doi.org/10.1145/2562059.2562141\">https://doi.org/10.1145/2562059.2562141</a>."},"year":"2014","oa":1,"date_updated":"2023-02-23T12:25:01Z","related_material":{"record":[{"id":"5409","relation":"earlier_version","status":"public"}]},"quality_controlled":"1","page":"303 - 312","department":[{"_id":"KrCh"}],"status":"public","date_published":"2014-01-01T00:00:00Z","type":"conference","publisher":"Springer","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus"},{"last_name":"Majumdar","full_name":"Majumdar, Ritankar","first_name":"Ritankar"}],"publication_status":"published","abstract":[{"lang":"eng","text":"The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in time stamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than δ away from the parameter, for δ &gt; 0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and analogous decidability results hold for rectangular automata."}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","day":"01","main_file_link":[{"url":"https://dl.acm.org/citation.cfm?doid=2562059.2562141","open_access":"1"}],"oa_version":"Submitted Version","month":"01","conference":{"end_date":"2017-04-17","location":"Berlin, Germany","start_date":"2017-04-15","name":"HSCC: Hybrid Systems - Computation and Control"}},{"title":"Markov decision processes with multiple long-run average objectives","issue":"1","date_updated":"2021-01-12T06:56:11Z","oa":1,"pubrep_id":"428","scopus_import":1,"intvolume":"        10","has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"Logical Methods in Computer Science","author":[{"last_name":"Brázdil","full_name":"Brázdil, Tomáš","first_name":"Tomáš"},{"last_name":"Brožek","first_name":"Václav","full_name":"Brožek, Václav"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Forejt","first_name":"Vojtěch","full_name":"Forejt, Vojtěch"},{"last_name":"Kučera","full_name":"Kučera, Antonín","first_name":"Antonín"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"system","access_level":"open_access","relation":"main_file","file_size":375388,"content_type":"application/pdf","checksum":"803edcc2d8c1acfba44a9ec43a5eb9f0","file_name":"IST-2016-428-v1+1_1104.3489.pdf","file_id":"4656","date_created":"2018-12-12T10:07:57Z","date_updated":"2020-07-14T12:45:34Z"}],"day":"14","main_file_link":[{"open_access":"1","url":"http://repository.ist.ac.at/id/eprint/428"}],"oa_version":"Published Version","publication_identifier":{"issn":["18605974"]},"month":"02","type":"journal_article","status":"public","citation":{"ama":"Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. Markov decision processes with multiple long-run average objectives. <i>Logical Methods in Computer Science</i>. 2014;10(1). doi:<a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">10.2168/LMCS-10(1:13)2014</a>","ieee":"T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, and A. Kučera, “Markov decision processes with multiple long-run average objectives,” <i>Logical Methods in Computer Science</i>, vol. 10, no. 1. International Federation of Computational Logic, 2014.","short":"T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, Logical Methods in Computer Science 10 (2014).","ista":"Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. 2014. Markov decision processes with multiple long-run average objectives. Logical Methods in Computer Science. 10(1).","chicago":"Brázdil, Tomáš, Václav Brožek, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Markov Decision Processes with Multiple Long-Run Average Objectives.” <i>Logical Methods in Computer Science</i>. International Federation of Computational Logic, 2014. <a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">https://doi.org/10.2168/LMCS-10(1:13)2014</a>.","mla":"Brázdil, Tomáš, et al. “Markov Decision Processes with Multiple Long-Run Average Objectives.” <i>Logical Methods in Computer Science</i>, vol. 10, no. 1, International Federation of Computational Logic, 2014, doi:<a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">10.2168/LMCS-10(1:13)2014</a>.","apa":"Brázdil, T., Brožek, V., Chatterjee, K., Forejt, V., &#38; Kučera, A. (2014). Markov decision processes with multiple long-run average objectives. <i>Logical Methods in Computer Science</i>. International Federation of Computational Logic. <a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">https://doi.org/10.2168/LMCS-10(1:13)2014</a>"},"publist_id":"4727","date_created":"2018-12-11T11:56:29Z","year":"2014","ec_funded":1,"_id":"2234","file_date_updated":"2020-07-14T12:45:34Z","doi":"10.2168/LMCS-10(1:13)2014","publication_status":"published","abstract":[{"lang":"eng","text":"We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with κ limit-average functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the case of one limit-average function, both randomization and memory are necessary for strategies even for ε-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized strategies are sufficient for ε-approximation, for all ε &gt; 0. We further prove that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be ε-approximated in time polynomial in the size of the MDP and 1/ε, and exponential in the number of limit-average functions, for all ε &gt; 0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","volume":10,"department":[{"_id":"KrCh"}],"date_published":"2014-02-14T00:00:00Z","publisher":"International Federation of Computational Logic"},{"publisher":"Elsevier","type":"journal_article","status":"public","date_published":"2014-02-13T00:00:00Z","page":"73 - 91","department":[{"_id":"KrCh"}],"volume":521,"quality_controlled":"1","publication_status":"published","author":[{"last_name":"Grinshpun","first_name":"Andrey","full_name":"Grinshpun, Andrey"},{"full_name":"Phalitnonkiat, Pakawat","first_name":"Pakawat","last_name":"Phalitnonkiat"},{"id":"2EC51194-F248-11E8-B48F-1D18A9856A87","last_name":"Rubin","first_name":"Sasha","full_name":"Rubin, Sasha"},{"last_name":"Tarfulea","full_name":"Tarfulea, Andrei","first_name":"Andrei"}],"month":"02","publication_identifier":{"issn":["03043975"]},"day":"13","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1303.3777"}],"oa_version":"Submitted Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. "}],"language":[{"iso":"eng"}],"_id":"2246","publication":"Theoretical Computer Science","doi":"10.1016/j.tcs.2013.11.032","oa":1,"date_updated":"2021-01-12T06:56:16Z","year":"2014","citation":{"ama":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. Alternating traps in Muller and parity games. <i>Theoretical Computer Science</i>. 2014;521:73-91. doi:<a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">10.1016/j.tcs.2013.11.032</a>","ieee":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, and A. Tarfulea, “Alternating traps in Muller and parity games,” <i>Theoretical Computer Science</i>, vol. 521. Elsevier, pp. 73–91, 2014.","short":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, A. Tarfulea, Theoretical Computer Science 521 (2014) 73–91.","mla":"Grinshpun, Andrey, et al. “Alternating Traps in Muller and Parity Games.” <i>Theoretical Computer Science</i>, vol. 521, Elsevier, 2014, pp. 73–91, doi:<a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">10.1016/j.tcs.2013.11.032</a>.","chicago":"Grinshpun, Andrey, Pakawat Phalitnonkiat, Sasha Rubin, and Andrei Tarfulea. “Alternating Traps in Muller and Parity Games.” <i>Theoretical Computer Science</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">https://doi.org/10.1016/j.tcs.2013.11.032</a>.","ista":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. 2014. Alternating traps in Muller and parity games. Theoretical Computer Science. 521, 73–91.","apa":"Grinshpun, A., Phalitnonkiat, P., Rubin, S., &#38; Tarfulea, A. (2014). Alternating traps in Muller and parity games. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">https://doi.org/10.1016/j.tcs.2013.11.032</a>"},"date_created":"2018-12-11T11:56:33Z","title":"Alternating traps in Muller and parity games","publist_id":"4703","scopus_import":1,"intvolume":"       521"},{"status":"public","type":"journal_article","arxiv":1,"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"full_name":"Randour, Mickael","first_name":"Mickael","last_name":"Randour"},{"last_name":"Raskin","first_name":"Jean","full_name":"Raskin, Jean"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1201.5073"}],"month":"06","language":[{"iso":"eng"}],"publication":"Acta Informatica","title":"Strategy synthesis for multi-dimensional quantitative objectives","article_processing_charge":"No","issue":"3-4","oa":1,"date_updated":"2023-02-21T16:06:56Z","intvolume":"        51","scopus_import":"1","project":[{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"}],"volume":51,"quality_controlled":"1","page":"129 - 163","department":[{"_id":"KrCh"}],"date_published":"2014-06-01T00:00:00Z","publisher":"Springer","publication_status":"published","abstract":[{"lang":"eng","text":"Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitative theory of verification and synthesis. In this work, we study the strategy synthesis problem for games with such multi-dimensional objectives along with a parity condition, a canonical way to express ω ω -regular conditions. While in general, the winning strategies in such games may require infinite memory, for synthesis the most relevant problem is the construction of a finite-memory winning strategy (if one exists). Our main contributions are as follows. First, we show a tight exponential bound (matching upper and lower bounds) on the memory required for finite-memory winning strategies in both multi-dimensional mean-payoff and energy games along with parity objectives. This significantly improves the triple exponential upper bound for multi energy games (without parity) that could be derived from results in literature for games on vector addition systems with states. Second, we present an optimal symbolic and incremental algorithm to compute a finite-memory winning strategy (if one exists) in such games. Finally, we give a complete characterization of when finite memory of strategies can be traded off for randomness. In particular, we show that for one-dimension mean-payoff parity games, randomized memoryless strategies are as powerful as their pure finite-memory counterparts."}],"external_id":{"arxiv":["1201.5073"]},"article_type":"original","_id":"2716","doi":"10.1007/s00236-013-0182-6","citation":{"apa":"Chatterjee, K., Randour, M., &#38; Raskin, J. (2014). Strategy synthesis for multi-dimensional quantitative objectives. <i>Acta Informatica</i>. Springer. <a href=\"https://doi.org/10.1007/s00236-013-0182-6\">https://doi.org/10.1007/s00236-013-0182-6</a>","ama":"Chatterjee K, Randour M, Raskin J. Strategy synthesis for multi-dimensional quantitative objectives. <i>Acta Informatica</i>. 2014;51(3-4):129-163. doi:<a href=\"https://doi.org/10.1007/s00236-013-0182-6\">10.1007/s00236-013-0182-6</a>","ieee":"K. Chatterjee, M. Randour, and J. Raskin, “Strategy synthesis for multi-dimensional quantitative objectives,” <i>Acta Informatica</i>, vol. 51, no. 3–4. Springer, pp. 129–163, 2014.","short":"K. Chatterjee, M. Randour, J. Raskin, Acta Informatica 51 (2014) 129–163.","chicago":"Chatterjee, Krishnendu, Mickael Randour, and Jean Raskin. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” <i>Acta Informatica</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00236-013-0182-6\">https://doi.org/10.1007/s00236-013-0182-6</a>.","ista":"Chatterjee K, Randour M, Raskin J. 2014. Strategy synthesis for multi-dimensional quantitative objectives. Acta Informatica. 51(3–4), 129–163.","mla":"Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” <i>Acta Informatica</i>, vol. 51, no. 3–4, Springer, 2014, pp. 129–63, doi:<a href=\"https://doi.org/10.1007/s00236-013-0182-6\">10.1007/s00236-013-0182-6</a>."},"publist_id":"4176","date_created":"2018-12-11T11:59:14Z","year":"2014","acknowledgement":"Krishnendu Chatterjee is supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407 (RiSE), ERC Starting Grant (279307: Graph Games) and Microsoft faculty fellowship. Mickael Randour is supported by F.R.S.-FNRS. fellowship. \r\nJean-François Raskin is supported by ERC Starting Grant (279499: inVEST).Thanks to D. Sbabo for useful pointers, V. Bruyère for comments on a preliminary draft, and A. Bohy for fruitful discussions about the Acacia+ tool. We are grateful to the anonymous reviewers for their insightful comments. ","related_material":{"record":[{"status":"public","id":"10904","relation":"earlier_version"}]}},{"doi":"10.4204/EPTCS.146.11","file_date_updated":"2020-07-14T12:46:35Z","_id":"475","ec_funded":1,"year":"2014","publist_id":"7345","citation":{"chicago":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, 146:83–90. Open Publishing Association, 2014. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>.","ista":"Aminof B, Rubin S. 2014. First cycle games. Electronic Proceedings in Theoretical Computer Science, EPTCS. SR: Strategic Reasoning, EPTCS, vol. 146, 83–90.","mla":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, vol. 146, Open Publishing Association, 2014, pp. 83–90, doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>.","ieee":"B. Aminof and S. Rubin, “First cycle games,” in <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, Grenoble, France, 2014, vol. 146, pp. 83–90.","ama":"Aminof B, Rubin S. First cycle games. In: <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>. Vol 146. Open Publishing Association; 2014:83-90. doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>","short":"B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.","apa":"Aminof, B., &#38; Rubin, S. (2014). First cycle games. In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i> (Vol. 146, pp. 83–90). Grenoble, France: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>"},"date_created":"2018-12-11T11:46:41Z","publisher":"Open Publishing Association","date_published":"2014-04-01T00:00:00Z","page":"83 - 90","department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":146,"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"call_identifier":"FWF","name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification"}],"ddc":["004"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"abstract":[{"text":"First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in Memoryless determinacy of parity and mean payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that θ (n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard. ","lang":"eng"}],"publication_status":"published","publication":"Electronic Proceedings in Theoretical Computer Science, EPTCS","language":[{"iso":"eng"}],"scopus_import":1,"intvolume":"       146","has_accepted_license":"1","pubrep_id":"952","oa":1,"date_updated":"2021-01-12T08:00:53Z","title":"First cycle games","alternative_title":["EPTCS"],"status":"public","type":"conference","conference":{"name":"SR: Strategic Reasoning","start_date":"2014-04-05","location":"Grenoble, France","end_date":"2014-04-06"},"month":"04","day":"01","oa_version":"Published Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","file":[{"content_type":"application/pdf","access_level":"open_access","file_size":100115,"relation":"main_file","creator":"system","date_created":"2018-12-12T10:17:08Z","date_updated":"2020-07-14T12:46:35Z","checksum":"4d7b4ab82980cca2b96ac7703992a8c8","file_id":"5260","file_name":"IST-2018-952-v1+1_2014_Rubin_First_cycle.pdf"}],"author":[{"last_name":"Aminof","id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","first_name":"Benjamin","full_name":"Aminof, Benjamin"},{"first_name":"Sasha","full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","last_name":"Rubin"}]},{"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10905"}]},"ec_funded":1,"year":"2014","date_created":"2018-12-11T11:47:01Z","publist_id":"7282","citation":{"ista":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2014. Polynomial-time algorithms for energy games with special weight structures. Algorithmica. 70(3), 457–492.","mla":"Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithmica</i>, vol. 70, no. 3, Springer, 2014, pp. 457–92, doi:<a href=\"https://doi.org/10.1007/s00453-013-9843-7\">10.1007/s00453-013-9843-7</a>.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithmica</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00453-013-9843-7\">https://doi.org/10.1007/s00453-013-9843-7</a>.","ama":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. <i>Algorithmica</i>. 2014;70(3):457-492. doi:<a href=\"https://doi.org/10.1007/s00453-013-9843-7\">10.1007/s00453-013-9843-7</a>","ieee":"K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” <i>Algorithmica</i>, vol. 70, no. 3. Springer, pp. 457–492, 2014.","short":"K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica 70 (2014) 457–492.","apa":"Chatterjee, K., Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2014). Polynomial-time algorithms for energy games with special weight structures. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-013-9843-7\">https://doi.org/10.1007/s00453-013-9843-7</a>"},"doi":"10.1007/s00453-013-9843-7","_id":"535","article_type":"original","abstract":[{"lang":"eng","text":"Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help."}],"external_id":{"arxiv":["1604.08234"]},"publication_status":"published","date_published":"2014-11-01T00:00:00Z","publisher":"Springer","quality_controlled":"1","volume":70,"department":[{"_id":"KrCh"}],"page":"457 - 492","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"intvolume":"        70","scopus_import":"1","issue":"3","article_processing_charge":"No","oa":1,"date_updated":"2023-09-05T14:09:29Z","title":"Polynomial-time algorithms for energy games with special weight structures","publication":"Algorithmica","language":[{"iso":"eng"}],"month":"11","user_id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd","main_file_link":[{"url":"https://arxiv.org/abs/1604.08234","open_access":"1"}],"oa_version":"Preprint","day":"01","arxiv":1,"author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"}],"type":"journal_article","status":"public"},{"month":"01","conference":{"name":"CAV: Computer Aided Verification","start_date":"2013-07-13","location":"St. Petersburg, Russia","end_date":"2013-07-19"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1303.5251"}],"oa_version":"Preprint","day":"01","arxiv":1,"author":[{"full_name":"Reiter, Johannes","first_name":"Johannes","orcid":"0000-0002-0170-7353","last_name":"Reiter","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Božić","first_name":"Ivana","full_name":"Božić, Ivana"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"type":"conference","status":"public","alternative_title":["LNCS"],"intvolume":"      8044","scopus_import":1,"date_updated":"2023-09-07T11:40:43Z","oa":1,"title":"TTP: Tool for tumor progression","publication":"Proceedings of 25th Int. Conf. on Computer Aided Verification","language":[{"iso":"eng"}],"series_title":"Lecture Notes in Computer Science","abstract":[{"text":"In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics.","lang":"eng"}],"external_id":{"arxiv":["1303.5251"]},"publication_status":"published","date_published":"2013-01-01T00:00:00Z","publisher":"Springer","volume":8044,"quality_controlled":"1","department":[{"_id":"KrCh"}],"page":"101 - 106","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"status":"public","id":"5399","relation":"earlier_version"},{"status":"public","id":"1400","relation":"dissertation_contains"}]},"ec_funded":1,"year":"2013","publist_id":"5077","date_created":"2018-12-11T11:55:08Z","citation":{"apa":"Reiter, J., Božić, I., Chatterjee, K., &#38; Nowak, M. (2013). TTP: Tool for tumor progression. In <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i> (Vol. 8044, pp. 101–106). St. Petersburg, Russia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">https://doi.org/10.1007/978-3-642-39799-8_6</a>","ieee":"J. Reiter, I. Božić, K. Chatterjee, and M. Nowak, “TTP: Tool for tumor progression,” in <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, St. Petersburg, Russia, 2013, vol. 8044, pp. 101–106.","ama":"Reiter J, Božić I, Chatterjee K, Nowak M. TTP: Tool for tumor progression. In: <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>. Vol 8044. Lecture Notes in Computer Science. Springer; 2013:101-106. doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">10.1007/978-3-642-39799-8_6</a>","short":"J. Reiter, I. Božić, K. Chatterjee, M. Nowak, in:, Proceedings of 25th Int. Conf. on Computer Aided Verification, Springer, 2013, pp. 101–106.","ista":"Reiter J, Božić I, Chatterjee K, Nowak M. 2013. TTP: Tool for tumor progression. Proceedings of 25th Int. Conf. on Computer Aided Verification. CAV: Computer Aided VerificationLecture Notes in Computer Science, LNCS, vol. 8044, 101–106.","chicago":"Reiter, Johannes, Ivana Božić, Krishnendu Chatterjee, and Martin Nowak. “TTP: Tool for Tumor Progression.” In <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, 8044:101–6. Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">https://doi.org/10.1007/978-3-642-39799-8_6</a>.","mla":"Reiter, Johannes, et al. “TTP: Tool for Tumor Progression.” <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, vol. 8044, Springer, 2013, pp. 101–06, doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">10.1007/978-3-642-39799-8_6</a>."},"doi":"10.1007/978-3-642-39799-8_6","_id":"2000"},{"has_accepted_license":"1","intvolume":"        23","scopus_import":1,"title":"Infinite-state games with finitary conditions","pubrep_id":"624","oa":1,"date_updated":"2021-01-12T06:50:14Z","publication":"22nd EACSL Annual Conference on Computer Science Logic","language":[{"iso":"eng"}],"file":[{"creator":"system","relation":"main_file","file_size":547296,"content_type":"application/pdf","access_level":"open_access","file_id":"5023","file_name":"IST-2016-624-v1+1_ChKr_Infinite-state_games_2013_17.pdf","checksum":"b7091a3866db573c0db5ec486952255e","date_updated":"2020-07-14T12:44:47Z","date_created":"2018-12-12T10:13:38Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"01","month":"09","conference":{"location":"Torino, Italy","end_date":"2013-09-05","name":"CSL: Computer Science Logic","start_date":"203-09-02"},"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Fijalkow","full_name":"Fijalkow, Nathanaël","first_name":"Nathanaël"}],"status":"public","type":"conference","alternative_title":["LIPIcs"],"ec_funded":1,"publist_id":"5837","citation":{"ama":"Chatterjee K, Fijalkow N. Infinite-state games with finitary conditions. In: <i>22nd EACSL Annual Conference on Computer Science Logic</i>. Vol 23. Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2013:181-196. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">10.4230/LIPIcs.CSL.2013.181</a>","ieee":"K. Chatterjee and N. Fijalkow, “Infinite-state games with finitary conditions,” in <i>22nd EACSL Annual Conference on Computer Science Logic</i>, Torino, Italy, 2013, vol. 23, pp. 181–196.","short":"K. Chatterjee, N. Fijalkow, in:, 22nd EACSL Annual Conference on Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–196.","chicago":"Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with Finitary Conditions.” In <i>22nd EACSL Annual Conference on Computer Science Logic</i>, 23:181–96. Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">https://doi.org/10.4230/LIPIcs.CSL.2013.181</a>.","mla":"Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with Finitary Conditions.” <i>22nd EACSL Annual Conference on Computer Science Logic</i>, vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–96, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">10.4230/LIPIcs.CSL.2013.181</a>.","ista":"Chatterjee K, Fijalkow N. 2013. Infinite-state games with finitary conditions. 22nd EACSL Annual Conference on Computer Science Logic. CSL: Computer Science LogicLeibniz International Proceedings in Informatics, LIPIcs, vol. 23, 181–196.","apa":"Chatterjee, K., &#38; Fijalkow, N. (2013). Infinite-state games with finitary conditions. In <i>22nd EACSL Annual Conference on Computer Science Logic</i> (Vol. 23, pp. 181–196). Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">https://doi.org/10.4230/LIPIcs.CSL.2013.181</a>"},"date_created":"2018-12-11T11:51:39Z","year":"2013","doi":"10.4230/LIPIcs.CSL.2013.181","_id":"1374","file_date_updated":"2020-07-14T12:44:47Z","abstract":[{"lang":"eng","text":"We study two-player zero-sum games over infinite-state graphs equipped with ωB and finitary conditions. Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory suffices for finitary parity games. We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with ωB-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"series_title":"Leibniz International Proceedings in Informatics","publication_status":"published","volume":23,"quality_controlled":"1","department":[{"_id":"KrCh"}],"page":"181 - 196","date_published":"2013-09-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","call_identifier":"FWF","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}]},{"language":[{"iso":"eng"}],"_id":"1376","doi":"10.1109/FMCAD.2013.6679386","publication":"13th International Conference on Formal Methods in Computer-Aided Design","date_created":"2018-12-11T11:51:40Z","publist_id":"5835","title":"Distributed synthesis for LTL fragments","citation":{"apa":"Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Pavlogiannis, A. (2013). Distributed synthesis for LTL fragments. In <i>13th International Conference on Formal Methods in Computer-Aided Design</i> (pp. 18–25). Portland, OR, United States: IEEE. <a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">https://doi.org/10.1109/FMCAD.2013.6679386</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. “Distributed Synthesis for LTL Fragments.” In <i>13th International Conference on Formal Methods in Computer-Aided Design</i>, 18–25. IEEE, 2013. <a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">https://doi.org/10.1109/FMCAD.2013.6679386</a>.","mla":"Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” <i>13th International Conference on Formal Methods in Computer-Aided Design</i>, IEEE, 2013, pp. 18–25, doi:<a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">10.1109/FMCAD.2013.6679386</a>.","ista":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL fragments. 13th International Conference on Formal Methods in Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, 18–25.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25.","ama":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis for LTL fragments. In: <i>13th International Conference on Formal Methods in Computer-Aided Design</i>. IEEE; 2013:18-25. doi:<a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">10.1109/FMCAD.2013.6679386</a>","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed synthesis for LTL fragments,” in <i>13th International Conference on Formal Methods in Computer-Aided Design</i>, Portland, OR, United States, 2013, pp. 18–25."},"year":"2013","date_updated":"2023-02-23T12:24:53Z","related_material":{"record":[{"id":"5406","relation":"earlier_version","status":"public"}]},"ec_funded":1,"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","call_identifier":"FP7","name":"Quantitative Reactive Modeling"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"page":"18 - 25","type":"conference","date_published":"2013-12-11T00:00:00Z","status":"public","publisher":"IEEE","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider the distributed synthesis problem for temporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTL and our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3) Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition."}],"day":"11","oa_version":"None","month":"12","conference":{"name":"FMCAD: Formal Methods in Computer-Aided Design","start_date":"2013-10-20","location":"Portland, OR, United States","end_date":"2013-10-23"}},{"type":"technical_report","date_published":"2013-01-11T00:00:00Z","status":"public","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"page":"17","department":[{"_id":"KrCh"}],"month":"01","publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"file":[{"checksum":"2cc8c6e157eca1271128db80bb3dec80","file_name":"IST-2013-104-v1+1_tumortool.pdf","file_id":"5542","date_created":"2018-12-12T11:54:20Z","date_updated":"2020-07-14T12:46:44Z","creator":"system","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":1471954}],"abstract":[{"text":"In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"11","oa_version":"Published Version","publication_status":"published","author":[{"full_name":"Reiter, Johannes","first_name":"Johannes","orcid":"0000-0002-0170-7353","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter"},{"first_name":"Ivana","full_name":"Bozic, Ivana","last_name":"Bozic"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"doi":"10.15479/AT:IST-2013-104-v1-1","language":[{"iso":"eng"}],"_id":"5399","file_date_updated":"2020-07-14T12:46:44Z","has_accepted_license":"1","related_material":{"record":[{"relation":"later_version","id":"2000","status":"public"}]},"year":"2013","oa":1,"pubrep_id":"104","date_updated":"2023-02-23T10:23:57Z","date_created":"2018-12-12T11:39:07Z","title":"TTP: Tool for Tumor Progression","citation":{"apa":"Reiter, J., Bozic, I., Chatterjee, K., &#38; Nowak, M. (2013). <i>TTP: Tool for Tumor Progression</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">https://doi.org/10.15479/AT:IST-2013-104-v1-1</a>","chicago":"Reiter, Johannes, Ivana Bozic, Krishnendu Chatterjee, and Martin Nowak. <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">https://doi.org/10.15479/AT:IST-2013-104-v1-1</a>.","ista":"Reiter J, Bozic I, Chatterjee K, Nowak M. 2013. TTP: Tool for Tumor Progression, IST Austria, 17p.","mla":"Reiter, Johannes, et al. <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">10.15479/AT:IST-2013-104-v1-1</a>.","short":"J. Reiter, I. Bozic, K. Chatterjee, M. Nowak, TTP: Tool for Tumor Progression, IST Austria, 2013.","ieee":"J. Reiter, I. Bozic, K. Chatterjee, and M. Nowak, <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013.","ama":"Reiter J, Bozic I, Chatterjee K, Nowak M. <i>TTP: Tool for Tumor Progression</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">10.15479/AT:IST-2013-104-v1-1</a>"}},{"publication_status":"published","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Martin","full_name":"Chmelik, Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Tracol","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","first_name":"Mathieu","full_name":"Tracol, Mathieu"}],"oa_version":"Published Version","day":"20","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"system","file_size":483407,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_name":"IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf","checksum":"cbba40210788a1b22c6cf06433b5ed6f","file_id":"5467","date_created":"2018-12-12T11:53:06Z","date_updated":"2020-07-14T12:46:44Z"}],"ddc":["000","005"],"month":"02","publication_identifier":{"issn":["2664-1690"]},"department":[{"_id":"KrCh"}],"page":"41","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"type":"technical_report","status":"public","date_published":"2013-02-20T00:00:00Z","title":"What is decidable about partially observable Markov decision processes with ω-regular objectives","date_created":"2018-12-12T11:39:07Z","citation":{"apa":"Chatterjee, K., Chmelik, M., &#38; Tracol, M. (2013). <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>","short":"K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013.","ama":"Chatterjee K, Chmelik M, Tracol M. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">10.15479/AT:IST-2013-109-v1-1</a>","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria, 2013.","ista":"Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with ω-regular objectives, IST Austria, 41p.","mla":"Chatterjee, Krishnendu, et al. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">10.15479/AT:IST-2013-109-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>."},"pubrep_id":"109","oa":1,"date_updated":"2023-02-23T10:36:45Z","year":"2013","related_material":{"record":[{"status":"public","id":"1477","relation":"later_version"},{"relation":"later_version","id":"2295","status":"public"}]},"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:44Z","language":[{"iso":"eng"}],"_id":"5400","doi":"10.15479/AT:IST-2013-109-v1-1"},{"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus"}],"publication_status":"published","abstract":[{"lang":"eng","text":"We consider concurrent games played by two-players on a finite state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to every transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of mean-payoff games) that is not known to be in polynomial time."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"system","content_type":"application/pdf","relation":"main_file","file_size":434523,"access_level":"open_access","checksum":"063868c665beec37bf28160e2a695746","file_id":"5510","file_name":"IST-2013-126-v1+1_soda_full.pdf","date_updated":"2020-07-14T12:46:45Z","date_created":"2018-12-12T11:53:49Z"}],"day":"03","oa_version":"Published Version","publication_identifier":{"issn":["2664-1690"]},"month":"07","ddc":["000","005"],"department":[{"_id":"KrCh"}],"page":"33","type":"technical_report","date_published":"2013-07-03T00:00:00Z","status":"public","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","title":"Qualitative analysis of concurrent mean-payoff games","date_created":"2018-12-12T11:39:08Z","citation":{"mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">10.15479/AT:IST-2013-126-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff games, IST Austria, 33p.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">https://doi.org/10.15479/AT:IST-2013-126-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, Qualitative Analysis of Concurrent Mean-Payoff Games, IST Austria, 2013.","ama":"Chatterjee K, Ibsen-Jensen R. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">10.15479/AT:IST-2013-126-v1-1</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>Qualitative analysis of concurrent mean-payoff games</i>. IST Austria, 2013.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2013). <i>Qualitative analysis of concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">https://doi.org/10.15479/AT:IST-2013-126-v1-1</a>"},"year":"2013","oa":1,"date_updated":"2023-02-23T12:22:53Z","pubrep_id":"126","has_accepted_license":"1","related_material":{"record":[{"id":"524","relation":"later_version","status":"public"}]},"language":[{"iso":"eng"}],"_id":"5403","file_date_updated":"2020-07-14T12:46:45Z","doi":"10.15479/AT:IST-2013-126-v1-1"},{"has_accepted_license":"1","related_material":{"record":[{"relation":"later_version","id":"2162","status":"public"}]},"pubrep_id":"127","date_updated":"2023-02-23T10:30:55Z","oa":1,"year":"2013","citation":{"apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2013). <i>The complexity of ergodic games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">https://doi.org/10.15479/AT:IST-2013-127-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013.","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Complexity of Ergodic Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">10.15479/AT:IST-2013-127-v1-1</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The complexity of ergodic games</i>. IST Austria, 2013.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">10.15479/AT:IST-2013-127-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">https://doi.org/10.15479/AT:IST-2013-127-v1-1</a>."},"date_created":"2018-12-12T11:39:08Z","title":"The complexity of ergodic games","doi":"10.15479/AT:IST-2013-127-v1-1","file_date_updated":"2020-07-14T12:46:45Z","_id":"5404","language":[{"iso":"eng"}],"ddc":["000","005"],"month":"07","publication_identifier":{"issn":["2664-1690"]},"oa_version":"Published Version","day":"03","file":[{"creator":"system","file_size":517275,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5496","file_name":"IST-2013-127-v1+1_ergodic.pdf","checksum":"79ee5e677a82611ce06e0360c69d494a","date_created":"2018-12-12T11:53:35Z","date_updated":"2020-07-14T12:46:45Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games."}],"publication_status":"published","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"date_published":"2013-07-03T00:00:00Z","status":"public","type":"technical_report","department":[{"_id":"KrCh"}],"page":"29"},{"oa_version":"Published Version","day":"08","abstract":[{"lang":"eng","text":"The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running\r\nin time O(d · n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the objective\r\ncan be ensured with probability 1, where n is the number of states of the game, d the number of priorities\r\nof the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states\r\nin 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems\r\nwith both functional requirement (given as a qualitative objective) and performance requirement (given\r\nas a quantitative objective)."}],"file":[{"content_type":"application/pdf","relation":"main_file","file_size":387467,"access_level":"open_access","creator":"system","date_created":"2018-12-12T11:53:54Z","date_updated":"2020-07-14T12:46:45Z","checksum":"ede787a10e74e4f7db302fab8f12f3ca","file_id":"5516","file_name":"IST-2013-128-v1+1_full_stoch_mpp.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000","005","510"],"publication_identifier":{"issn":["2664-1690"]},"month":"07","publication_status":"published","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Laurent","full_name":"Doyen, Laurent","last_name":"Doyen"},{"last_name":"Gimbert","first_name":"Hugo","full_name":"Gimbert, Hugo"},{"full_name":"Oualhadj, Youssouf","first_name":"Youssouf","last_name":"Oualhadj"}],"page":"22","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","type":"technical_report","date_published":"2013-07-08T00:00:00Z","status":"public","has_accepted_license":"1","related_material":{"record":[{"relation":"later_version","id":"2212","status":"public"}]},"citation":{"apa":"Chatterjee, K., Doyen, L., Gimbert, H., &#38; Oualhadj, Y. (2013). <i>Perfect-information stochastic mean-payoff parity games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">https://doi.org/10.15479/AT:IST-2013-128-v1-1</a>","ama":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">10.15479/AT:IST-2013-128-v1-1</a>","ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, <i>Perfect-information stochastic mean-payoff parity games</i>. IST Austria, 2013.","short":"K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, Perfect-Information Stochastic Mean-Payoff Parity Games, IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">https://doi.org/10.15479/AT:IST-2013-128-v1-1</a>.","ista":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2013. Perfect-information stochastic mean-payoff parity games, IST Austria, 22p.","mla":"Chatterjee, Krishnendu, et al. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">10.15479/AT:IST-2013-128-v1-1</a>."},"title":"Perfect-information stochastic mean-payoff parity games","date_created":"2018-12-12T11:39:09Z","date_updated":"2023-02-23T10:33:08Z","oa":1,"pubrep_id":"128","year":"2013","doi":"10.15479/AT:IST-2013-128-v1-1","file_date_updated":"2020-07-14T12:46:45Z","_id":"5405","language":[{"iso":"eng"}]}]