[{"article_processing_charge":"No","file_date_updated":"2020-07-14T12:46:00Z","date_published":"2012-10-01T00:00:00Z","has_accepted_license":"1","fulldoi":"https://doi.org/10.1007/s10703-012-0164-2","ddc":["005"],"intvolume":"        43","year":"2012","quality_controlled":"1","publication_status":"published","isi":1,"file":[{"access_level":"open_access","creator":"system","relation":"main_file","date_created":"2018-12-12T10:11:27Z","checksum":"dd3d590f383bb2ac6cfda1489ac1c42a","date_updated":"2020-07-14T12:46:00Z","content_type":"application/pdf","file_name":"IST-2014-303-v1+1_Survey_Partial-Observation_Stochastic_Parity_Games.pdf","file_size":163983,"file_id":"4882"}],"doi":"10.1007/s10703-012-0164-2","volume":43,"pubrep_id":"303","corr_author":"1","oa":1,"day":"01","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"month":"10","publisher":"Springer","external_id":{"isi":["000324114600006"]},"project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"page":"268 - 284","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “A Survey of Partial-Observation Stochastic Parity Games.” <i>Formal Methods in System Design</i>. Springer, 2012. <a href=\"https://doi.org/10.1007/s10703-012-0164-2\">https://doi.org/10.1007/s10703-012-0164-2</a>.","apa":"Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2012). A survey of partial-observation stochastic parity games. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-012-0164-2\">https://doi.org/10.1007/s10703-012-0164-2</a>","ama":"Chatterjee K, Doyen L, Henzinger TA. A survey of partial-observation stochastic parity games. <i>Formal Methods in System Design</i>. 2012;43(2):268-284. doi:<a href=\"https://doi.org/10.1007/s10703-012-0164-2\">10.1007/s10703-012-0164-2</a>","mla":"Chatterjee, Krishnendu, et al. “A Survey of Partial-Observation Stochastic Parity Games.” <i>Formal Methods in System Design</i>, vol. 43, no. 2, Springer, 2012, pp. 268–84, doi:<a href=\"https://doi.org/10.1007/s10703-012-0164-2\">10.1007/s10703-012-0164-2</a>.","ista":"Chatterjee K, Doyen L, Henzinger TA. 2012. A survey of partial-observation stochastic parity games. Formal Methods in System Design. 43(2), 268–284.","ieee":"K. Chatterjee, L. Doyen, and T. A. Henzinger, “A survey of partial-observation stochastic parity games,” <i>Formal Methods in System Design</i>, vol. 43, no. 2. Springer, pp. 268–284, 2012.","short":"K. Chatterjee, L. Doyen, T.A. Henzinger, Formal Methods in System Design 43 (2012) 268–284."},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-30T07:57:51Z","date_created":"2018-12-11T12:01:33Z","status":"public","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"}],"_id":"3128","title":"A survey of partial-observation stochastic parity games","abstract":[{"lang":"eng","text":"We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. 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. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational). "}],"type":"journal_article","oa_version":"Submitted Version","language":[{"iso":"eng"}],"publist_id":"3570","issue":"2","scopus_import":"1","publication":"Formal Methods in System Design","ec_funded":1,"acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF NFN Grant No. S11407-N23(RiSE), ERC Start grant (279307: Graph Games), Microsoft faculty fellows award, ERC Advanced grant QUAREM, and FWF Grant No. S11403-N23 (RiSE)."},{"project":[{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","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"}],"citation":{"apa":"Brázdil, B., Chatterjee, K., Kučera, A., &#38; Novotný, P. (2012). Efficient controller synthesis for consumption games with multiple resource types (Vol. 7358, pp. 23–38). Presented at the CAV: Computer Aided Verification, Berkeley, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">https://doi.org/10.1007/978-3-642-31424-7_8</a>","chicago":"Brázdil, Brázdil, Krishnendu Chatterjee, Antonín Kučera, and Petr Novotný. “Efficient Controller Synthesis for Consumption Games with Multiple Resource Types,” 7358:23–38. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">https://doi.org/10.1007/978-3-642-31424-7_8</a>.","short":"B. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, in:, Springer, 2012, pp. 23–38.","ieee":"B. Brázdil, K. Chatterjee, A. Kučera, and P. Novotný, “Efficient controller synthesis for consumption games with multiple resource types,” presented at the CAV: Computer Aided Verification, Berkeley, CA, USA, 2012, vol. 7358, pp. 23–38.","ista":"Brázdil B, Chatterjee K, Kučera A, Novotný P. 2012. Efficient controller synthesis for consumption games with multiple resource types. CAV: Computer Aided Verification, LNCS, vol. 7358, 23–38.","ama":"Brázdil B, Chatterjee K, Kučera A, Novotný P. Efficient controller synthesis for consumption games with multiple resource types. In: Vol 7358. Springer; 2012:23-38. doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">10.1007/978-3-642-31424-7_8</a>","mla":"Brázdil, Brázdil, et al. <i>Efficient Controller Synthesis for Consumption Games with Multiple Resource Types</i>. Vol. 7358, Springer, 2012, pp. 23–38, doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">10.1007/978-3-642-31424-7_8</a>."},"page":"23 - 38","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-06-11T08:10:20Z","_id":"3135","title":"Efficient controller synthesis for consumption games with multiple resource types","status":"public","author":[{"first_name":"Brázdil","last_name":"Brázdil","full_name":"Brázdil, Brázdil"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Antonín","last_name":"Kučera","full_name":"Kučera, Antonín"},{"full_name":"Novotny, Petr","first_name":"Petr","last_name":"Novotny","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-11T12:01:35Z","type":"conference","oa_version":"Preprint","abstract":[{"text":"We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates. ","lang":"eng"}],"publist_id":"3562","language":[{"iso":"eng"}],"scopus_import":"1","acknowledgement":"Tomas Brazdil, Antonin Kucera, and Petr Novotny are supported by the Czech Science Foundation, grant No. P202/10/1469. Krishnendu Chatterjee is supported by the FWF (Austrian Science Fund) NFN Grant No S11407-N23 (RiSE) and ERC Start grant (279307: Graph Games).","ec_funded":1,"alternative_title":["LNCS"],"date_published":"2012-07-01T00:00:00Z","conference":{"name":"CAV: Computer Aided Verification","end_date":"2012-07-13","start_date":"2012-07-07","location":"Berkeley, CA, USA"},"article_processing_charge":"No","fulldoi":"https://doi.org/10.1007/978-3-642-31424-7_8","arxiv":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1202.0796"}],"quality_controlled":"1","year":"2012","publication_status":"published","intvolume":"      7358","volume":7358,"doi":"10.1007/978-3-642-31424-7_8","day":"01","oa":1,"external_id":{"arxiv":["1202.0796"]},"month":"07","department":[{"_id":"KrCh"}],"publisher":"Springer"},{"type":"conference","oa_version":"Preprint","abstract":[{"lang":"eng","text":"Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m &gt; n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m &gt; n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem."}],"_id":"3165","title":"An O(n2) time algorithm for alternating Büchi games","status":"public","date_created":"2018-12-11T12:01:46Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-09-29T11:45:12Z","related_material":{"record":[{"status":"public","id":"5379","relation":"earlier_version"},{"relation":"later_version","id":"2141","status":"public"}]},"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307"},{"grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"citation":{"apa":"Chatterjee, K., &#38; Henzinger, M. (2012). An O(n2) time algorithm for alternating Büchi games. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1386–1399). Kyoto, Japan: SIAM. <a href=\"https://doi.org/10.1137/1.9781611973099.109\">https://doi.org/10.1137/1.9781611973099.109</a>","chicago":"Chatterjee, Krishnendu, and Monika Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1386–99. SIAM, 2012. <a href=\"https://doi.org/10.1137/1.9781611973099.109\">https://doi.org/10.1137/1.9781611973099.109</a>.","ieee":"K. Chatterjee and M. Henzinger, “An O(n2) time algorithm for alternating Büchi games,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Kyoto, Japan, 2012, pp. 1386–1399.","short":"K. Chatterjee, M. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.","ista":"Chatterjee K, Henzinger M. 2012. An O(n2) time algorithm for alternating Büchi games. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1386–1399.","ama":"Chatterjee K, Henzinger M. An O(n2) time algorithm for alternating Büchi games. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. SIAM; 2012:1386-1399. doi:<a href=\"https://doi.org/10.1137/1.9781611973099.109\">10.1137/1.9781611973099.109</a>","mla":"Chatterjee, Krishnendu, and Monika Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, SIAM, 2012, pp. 1386–99, doi:<a href=\"https://doi.org/10.1137/1.9781611973099.109\">10.1137/1.9781611973099.109</a>."},"page":"1386 - 1399","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, Vienna Science and Technology Fund (WWTF) Grant ICT10-002, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","ec_funded":1,"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","language":[{"iso":"eng"}],"publist_id":"3519","OA_place":"repository","OA_type":"green","year":"2012","quality_controlled":"1","publication_status":"published","fulldoi":"https://doi.org/10.1137/1.9781611973099.109","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1109.5018"}],"date_published":"2012-01-01T00:00:00Z","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2012-01-19","start_date":"2012-01-17","location":"Kyoto, Japan"},"article_processing_charge":"No","external_id":{"arxiv":["1109.5018"]},"department":[{"_id":"KrCh"}],"month":"01","publisher":"SIAM","day":"01","pubrep_id":"15","corr_author":"1","oa":1,"doi":"10.1137/1.9781611973099.109"},{"fulldoi":"https://doi.org/10.1007/978-3-642-27940-9_11","arxiv":1,"main_file_link":[{"url":"https://arxiv.org/abs/1004.2697","open_access":"1"}],"alternative_title":["LNCS"],"date_published":"2012-01-20T00:00:00Z","conference":{"end_date":"2012-01-24","start_date":"2012-01-22","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","location":"Philadelphia, PA, USA"},"article_processing_charge":"No","year":"2012","quality_controlled":"1","publication_status":"published","intvolume":"      7148","volume":7148,"doi":"10.1007/978-3-642-27940-9_11","external_id":{"arxiv":["1004.2697"]},"department":[{"_id":"KrCh"}],"month":"01","publisher":"Springer","day":"20","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-06-11T08:06:25Z","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":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"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"}],"page":"152 - 168","citation":{"apa":"Chatterjee, K., &#38; Raman, V. (2012). Synthesizing protocols for digital contract signing (Vol. 7148, pp. 152–168). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>","chicago":"Chatterjee, Krishnendu, and Vishwanath Raman. “Synthesizing Protocols for Digital Contract Signing,” 7148:152–68. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>.","ieee":"K. Chatterjee and V. Raman, “Synthesizing protocols for digital contract signing,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 152–168.","ista":"Chatterjee K, Raman V. 2012. Synthesizing protocols for digital contract signing. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 152–168.","short":"K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 152–168.","mla":"Chatterjee, Krishnendu, and Vishwanath Raman. <i>Synthesizing Protocols for Digital Contract Signing</i>. Vol. 7148, Springer, 2012, pp. 152–68, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>.","ama":"Chatterjee K, Raman V. Synthesizing protocols for digital contract signing. In: Vol 7148. Springer; 2012:152-168. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>"},"type":"conference","oa_version":"Preprint","abstract":[{"text":"We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents, the trusted third party (TTP) and the protocols as path formulas in Linear Temporal Logic (LTL) and prove that the satisfaction of the objectives of the agents and the TTP imply satisfaction of the protocol objectives. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail in synthesizing these protocols, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee synthesis is attack-free; no subset of participants can violate the objectives of the other participants without violating their own objectives; (b) the Asokan-Shoup-Waidner (ASW) certified mail protocol that has known vulnerabilities is not a solution of AGS; and (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution of AGS. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can generate correct protocols and automatically discover vulnerabilities. The solution to assume-guarantee synthesis can be computed efficiently as the secure equilibrium solution of three-player graph games. © 2012 Springer-Verlag.","lang":"eng"}],"_id":"3252","title":"Synthesizing protocols for digital contract signing","date_created":"2018-12-11T12:02:16Z","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Raman, Vishwanath","last_name":"Raman","first_name":"Vishwanath"}],"status":"public","publist_id":"3405","language":[{"iso":"eng"}],"ec_funded":1,"acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 (Modern Graph Algorithmic Techniques in Formal Verification), FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nThe authors would like to thank Avik Chaudhuri for his invaluable help and feedback.","scopus_import":"1"},{"citation":{"chicago":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” <i>Information and Computation</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">https://doi.org/10.1016/j.ic.2011.11.004</a>.","apa":"Chatterjee, K. (2012). The complexity of stochastic Müller games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">https://doi.org/10.1016/j.ic.2011.11.004</a>","ama":"Chatterjee K. The complexity of stochastic Müller games. <i>Information and Computation</i>. 2012;211:29-48. doi:<a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">10.1016/j.ic.2011.11.004</a>","mla":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” <i>Information and Computation</i>, vol. 211, Elsevier, 2012, pp. 29–48, doi:<a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">10.1016/j.ic.2011.11.004</a>.","ieee":"K. Chatterjee, “The complexity of stochastic Müller games,” <i>Information and Computation</i>, vol. 211. Elsevier, pp. 29–48, 2012.","short":"K. Chatterjee, Information and Computation 211 (2012) 29–48.","ista":"Chatterjee K. 2012. The complexity of stochastic Müller games. Information and Computation. 211, 29–48."},"page":"29 - 48","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"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"}],"date_updated":"2025-09-30T07:45:01Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"The complexity of stochastic Müller games","_id":"3254","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"}],"date_created":"2018-12-11T12:02:17Z","status":"public","type":"journal_article","oa_version":"None","abstract":[{"text":"The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also study the complexity of stochastic Müller games and show that both the qualitative and quantitative analysis problems are PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes.","lang":"eng"}],"publist_id":"3403","language":[{"iso":"eng"}],"publication":"Information and Computation","scopus_import":"1","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","ec_funded":1,"date_published":"2012-02-01T00:00:00Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.1016/j.ic.2011.11.004","main_file_link":[{"url":"http://arise.or.at/pubpdf/The_complexity_of_stochastic_M___u_ller_games.pdf"}],"publication_status":"published","quality_controlled":"1","year":"2012","intvolume":"       211","isi":1,"volume":211,"doi":"10.1016/j.ic.2011.11.004","day":"01","corr_author":"1","external_id":{"isi":["000300468000002"]},"publisher":"Elsevier","month":"02","department":[{"_id":"KrCh"}]},{"publist_id":"3400","language":[{"iso":"eng"}],"acknowledgement":"This work was partially supported by FWF NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","scopus_import":1,"date_updated":"2021-01-12T07:42:10Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"37 - 46","citation":{"apa":"Chatterjee, K., &#38; Doyen, L. (2012). Games and Markov decision processes with mean payoff parity and energy parity objectives (Vol. 7119, pp. 37–46). Presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives,” 7119:37–46. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>.","ieee":"K. Chatterjee and L. Doyen, “Games and Markov decision processes with mean payoff parity and energy parity objectives,” presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic, 2012, vol. 7119, pp. 37–46.","ista":"Chatterjee K, Doyen L. 2012. Games and Markov decision processes with mean payoff parity and energy parity objectives. MEMICS: Mathematical and Engineering Methods in Computer Science, LNCS, vol. 7119, 37–46.","short":"K. Chatterjee, L. Doyen, in:, Springer, 2012, pp. 37–46.","ama":"Chatterjee K, Doyen L. Games and Markov decision processes with mean payoff parity and energy parity objectives. In: Vol 7119. Springer; 2012:37-46. doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives</i>. Vol. 7119, Springer, 2012, pp. 37–46, doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>."},"project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"abstract":[{"lang":"eng","text":"In this paper we survey results of two-player games on graphs and Markov decision processes with parity, mean-payoff and energy objectives, and the combination of mean-payoff and energy objectives with parity objectives. These problems have applications in verification and synthesis of reactive systems in resource-constrained environments."}],"oa_version":"Submitted Version","type":"conference","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}],"status":"public","date_created":"2018-12-11T12:02:17Z","title":"Games and Markov decision processes with mean payoff parity and energy parity objectives","_id":"3255","doi":"10.1007/978-3-642-25929-6_3","file":[{"file_size":114060,"content_type":"application/pdf","date_updated":"2020-07-14T12:46:05Z","file_name":"2012_MEMICS_Chatterjee.pdf","file_id":"7863","creator":"dernst","relation":"main_file","access_level":"open_access","date_created":"2020-05-15T12:53:12Z","checksum":"eed2cc1e76b160418c977e76e8899a60"}],"volume":7119,"publisher":"Springer","department":[{"_id":"KrCh"}],"month":"01","oa":1,"day":"01","fulldoi":"https://doi.org/10.1007/978-3-642-25929-6_3","article_processing_charge":"No","conference":{"end_date":"2011-10-16","start_date":"2011-10-14","name":"MEMICS: Mathematical and Engineering Methods in Computer Science","location":"Lednice, Czech Republic"},"has_accepted_license":"1","alternative_title":["LNCS"],"date_published":"2012-01-01T00:00:00Z","file_date_updated":"2020-07-14T12:46:05Z","intvolume":"      7119","publication_status":"published","quality_controlled":"1","year":"2012","ddc":["000"]},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-30T07:38:00Z","project":[{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"page":"609 - 625","citation":{"apa":"Chatterjee, K., &#38; Majumdar, R. (2012). Discounting and averaging in games across time scales. <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing. <a href=\"https://doi.org/10.1142/S0129054112400308\">https://doi.org/10.1142/S0129054112400308</a>","chicago":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing, 2012. <a href=\"https://doi.org/10.1142/S0129054112400308\">https://doi.org/10.1142/S0129054112400308</a>.","ieee":"K. Chatterjee and R. Majumdar, “Discounting and averaging in games across time scales,” <i>International Journal of Foundations of Computer Science</i>, vol. 23, no. 3. World Scientific Publishing, pp. 609–625, 2012.","ista":"Chatterjee K, Majumdar R. 2012. Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science. 23(3), 609–625.","short":"K. Chatterjee, R. Majumdar, International Journal of Foundations of Computer Science 23 (2012) 609–625.","ama":"Chatterjee K, Majumdar R. Discounting and averaging in games across time scales. <i>International Journal of Foundations of Computer Science</i>. 2012;23(3):609-625. doi:<a href=\"https://doi.org/10.1142/S0129054112400308\">10.1142/S0129054112400308</a>","mla":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” <i>International Journal of Foundations of Computer Science</i>, vol. 23, no. 3, World Scientific Publishing, 2012, pp. 609–25, doi:<a href=\"https://doi.org/10.1142/S0129054112400308\">10.1142/S0129054112400308</a>."},"abstract":[{"lang":"eng","text":"We introduce two-level discounted and mean-payoff games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted or mean-payoff game and the lower level game is a (undiscounted) reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. For both discounted and mean-payoff two-level games, we show the existence of pure memoryless optimal strategies for both players and an ordered field property. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted or mean-payoff games can be decided in NP ∩ coNP. We also give an alternate strategy improvement algorithm to compute the value. © 2012 World Scientific Publishing Company."}],"type":"journal_article","oa_version":"None","status":"public","date_created":"2018-12-11T12:02:37Z","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Majumdar, Ritankar","first_name":"Ritankar","last_name":"Majumdar"}],"_id":"3314","title":"Discounting and averaging in games across time scales","publist_id":"3326","language":[{"iso":"eng"}],"acknowledgement":"This research was funded in part by the US National Science Foundation grants CCF-0546170, CNS-0702881, DARPA grant HR0011-09-1-0037, Austrian Science Fund (FWF) NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","issue":"3","scopus_import":"1","publication":"International Journal of Foundations of Computer Science","fulldoi":"https://doi.org/10.1142/S0129054112400308","article_processing_charge":"No","date_published":"2012-04-01T00:00:00Z","intvolume":"        23","year":"2012","quality_controlled":"1","publication_status":"published","doi":"10.1142/S0129054112400308","volume":23,"isi":1,"month":"04","department":[{"_id":"KrCh"}],"publisher":"World Scientific Publishing","external_id":{"isi":["000304003000004"]},"day":"01"},{"scopus_import":1,"ec_funded":1,"publist_id":"3284","language":[{"iso":"eng"}],"_id":"3341","title":"Robustness of structurally equivalent concurrent parity games","date_created":"2018-12-11T12:02:46Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"}],"status":"public","oa_version":"Preprint","type":"conference","abstract":[{"text":"We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \\omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).","lang":"eng"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5382"}]},"project":[{"grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"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"}],"citation":{"ista":"Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213, 270–285.","short":"K. Chatterjee, in:, Springer, 2012, pp. 270–285.","ieee":"K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia, 2012, vol. 7213, pp. 270–285.","mla":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. Vol. 7213, Springer, 2012, pp. 270–85, doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>.","ama":"Chatterjee K. Robustness of structurally equivalent concurrent parity games. In: Vol 7213. Springer; 2012:270-285. doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>","apa":"Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>","chicago":"Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent Parity Games,” 7213:270–85. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>."},"page":"270 - 285","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-10-09T20:54:38Z","day":"22","corr_author":"1","oa":1,"external_id":{"arxiv":["1107.2009"]},"month":"03","department":[{"_id":"KrCh"}],"publisher":"Springer","volume":7213,"doi":"10.1007/978-3-642-28729-9_18","year":"2012","quality_controlled":"1","publication_status":"published","intvolume":"      7213","alternative_title":["LNCS"],"date_published":"2012-03-22T00:00:00Z","conference":{"location":"Tallinn, Estonia","name":"FoSSaCS: Foundations of Software Science and Computation Structures","end_date":"2012-04-01","start_date":"2012-03-24"},"fulldoi":"https://doi.org/10.1007/978-3-642-28729-9_18","arxiv":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.2009"}]},{"day":"02","oa":1,"corr_author":"1","external_id":{"isi":["000299719100002"]},"publisher":"Elsevier","month":"03","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"isi":1,"volume":78,"doi":"10.1016/j.jcss.2011.05.002","file":[{"date_updated":"2020-07-14T12:46:17Z","content_type":"application/pdf","file_name":"a_survey_of_stochastic_omega-regular_games.pdf","file_size":336450,"file_id":"5897","access_level":"open_access","relation":"main_file","creator":"kschuh","date_created":"2019-01-29T10:54:28Z","checksum":"241b939deb4517cdd4426d49c67e3fa2"}],"ddc":["000"],"publication_status":"published","quality_controlled":"1","year":"2012","intvolume":"        78","has_accepted_license":"1","date_published":"2012-03-02T00:00:00Z","file_date_updated":"2020-07-14T12:46:17Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.1016/j.jcss.2011.05.002","main_file_link":[{"url":"https://doi.org/10.1016/j.jcss.2011.05.002","open_access":"1"}],"publication":"Journal of Computer and System Sciences","scopus_import":"1","issue":"2","acknowledgement":"This research was supported in part by the ONR grant N00014-02-1-0671, by the AFOSR MURI grant F49620-00-1-0327, and by the NSF grants CCR-9988172, CCR-0085949, and CCR-0225610.","publist_id":"2341","language":[{"iso":"eng"}],"title":"A survey of stochastic ω regular games","_id":"3846","date_created":"2018-12-11T12:05:29Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"status":"public","oa_version":"Submitted Version","type":"journal_article","article_type":"original","abstract":[{"lang":"eng","text":"We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications."}],"citation":{"short":"K. Chatterjee, T.A. Henzinger, Journal of Computer and System Sciences 78 (2012) 394–413.","ista":"Chatterjee K, Henzinger TA. 2012. A survey of stochastic ω regular games. Journal of Computer and System Sciences. 78(2), 394–413.","ieee":"K. Chatterjee and T. A. Henzinger, “A survey of stochastic ω regular games,” <i>Journal of Computer and System Sciences</i>, vol. 78, no. 2. Elsevier, pp. 394–413, 2012.","mla":"Chatterjee, Krishnendu, and Thomas A. Henzinger. “A Survey of Stochastic ω Regular Games.” <i>Journal of Computer and System Sciences</i>, vol. 78, no. 2, Elsevier, 2012, pp. 394–413, doi:<a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">10.1016/j.jcss.2011.05.002</a>.","ama":"Chatterjee K, Henzinger TA. A survey of stochastic ω regular games. <i>Journal of Computer and System Sciences</i>. 2012;78(2):394-413. doi:<a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">10.1016/j.jcss.2011.05.002</a>","apa":"Chatterjee, K., &#38; Henzinger, T. A. (2012). A survey of stochastic ω regular games. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">https://doi.org/10.1016/j.jcss.2011.05.002</a>","chicago":"Chatterjee, Krishnendu, and Thomas A Henzinger. “A Survey of Stochastic ω Regular Games.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">https://doi.org/10.1016/j.jcss.2011.05.002</a>."},"page":"394 - 413","date_updated":"2025-09-30T07:32:39Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"fulldoi":"https://doi.org/10.1109/LICS.2012.28","main_file_link":[{"url":"http://arxiv.org/abs/1107.2141","open_access":"1"}],"arxiv":1,"conference":{"name":"LICS: Logic in Computer Science","end_date":"2012-06-28","start_date":"2012-06-25","location":"Dubrovnik, Croatia"},"date_published":"2012-08-23T00:00:00Z","article_processing_charge":"No","publication_status":"published","quality_controlled":"1","year":"2012","doi":"10.1109/LICS.2012.28","isi":1,"article_number":"6280436","external_id":{"isi":["000309059900023"],"arxiv":["1107.2141"]},"publisher":"IEEE","month":"08","department":[{"_id":"KrCh"}],"day":"23","oa":1,"date_updated":"2026-07-07T14:01:25Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","related_material":{"record":[{"status":"public","id":"5381","relation":"earlier_version"},{"status":"public","relation":"later_version","id":"2211"}]},"citation":{"ista":"Chatterjee K, Doyen L. 2012. Partial-observation stochastic games: How to win when belief fails. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280436.","ieee":"K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to win when belief fails,” in <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Dubrovnik, Croatia, 2012.","short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 6280436, IEEE, 2012, doi:<a href=\"https://doi.org/10.1109/LICS.2012.28\">10.1109/LICS.2012.28</a>.","ama":"Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when belief fails. In: <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2012. doi:<a href=\"https://doi.org/10.1109/LICS.2012.28\">10.1109/LICS.2012.28</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2012). Partial-observation stochastic games: How to win when belief fails. In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Dubrovnik, Croatia: IEEE. <a href=\"https://doi.org/10.1109/LICS.2012.28\">https://doi.org/10.1109/LICS.2012.28</a>","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE, 2012. <a href=\"https://doi.org/10.1109/LICS.2012.28\">https://doi.org/10.1109/LICS.2012.28</a>."},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","type":"conference","abstract":[{"lang":"eng","text":"We consider two-player stochastic games played on finite graphs with 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 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, the players (a) may not be allowed to use randomization (pure strategies), or (b) may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) may use full randomization. Our main results for pure strategies are as follows. (1) For one-sided games with player 1 having partial 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 almostsure 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. (2) For one-sided games with player 2 having partial observation we show that non-elementary memory 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 non-elementary 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 exhibits serious flaws in previous results of the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed."}],"title":"Partial-observation stochastic games: How to win when belief fails","_id":"2955","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"date_created":"2018-12-11T12:00:32Z","status":"public","language":[{"iso":"eng"}],"publist_id":"3771","acknowledgement":"This work was partially supported by FWF Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","ec_funded":1,"publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","scopus_import":"1"},{"language":[{"iso":"eng"}],"ec_funded":1,"publication_identifier":{"isbn":["9783642330896"],"eisbn":["9783642330902"],"issn":["0302-9743"],"eissn":["1611-3349"]},"acknowledgement":"Supported by the Austrian Science Fund (FWF): P23499-N23, the Austrian Science Fund (FWF): S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award","publication":"20th Annual European Symposium on Algorithms ","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-07-08T05:50:39Z","related_material":{"record":[{"status":"public","id":"535","relation":"later_version"}]},"project":[{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory","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"}],"page":"301-312","citation":{"chicago":"Chatterjee, Krishnendu, Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” In <i>20th Annual European Symposium on Algorithms </i>, 7501:301–12. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">https://doi.org/10.1007/978-3-642-33090-2_27</a>.","apa":"Chatterjee, K., Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2012). Polynomial-time algorithms for energy games with special weight structures. In <i>20th Annual European Symposium on Algorithms </i> (Vol. 7501, pp. 301–312). Ljubljana, Slovenia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">https://doi.org/10.1007/978-3-642-33090-2_27</a>","mla":"Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>20th Annual European Symposium on Algorithms </i>, vol. 7501, Springer, 2012, pp. 301–12, doi:<a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">10.1007/978-3-642-33090-2_27</a>.","ama":"Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. In: <i>20th Annual European Symposium on Algorithms </i>. Vol 7501. Springer; 2012:301-312. doi:<a href=\"https://doi.org/10.1007/978-3-642-33090-2_27\">10.1007/978-3-642-33090-2_27</a>","ista":"Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. 2012. Polynomial-time algorithms for energy games with special weight structures. 20th Annual European Symposium on Algorithms . ESA: European Symposium on Algorithms, LNCS, vol. 7501, 301–312.","short":"K. Chatterjee, M. Henzinger, S. Krinninger, D. Nanongkai, in:, 20th Annual European Symposium on Algorithms , Springer, 2012, pp. 301–312.","ieee":"K. Chatterjee, M. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” in <i>20th Annual European Symposium on Algorithms </i>, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312."},"oa_version":"Preprint","type":"conference","abstract":[{"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. While the existence of polynomial-time algorithms has been a major open problem for decades, there is no algorithm that solves any non-trivial subclass in polynomial time.\r\nIn 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 counter examples that show that many 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 graph structures need not help.","lang":"eng"}],"_id":"10905","title":"Polynomial-time algorithms for energy games with special weight structures","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"status":"public","date_created":"2022-03-21T08:01:45Z","volume":7501,"doi":"10.1007/978-3-642-33090-2_27","external_id":{"arxiv":["1604.08234"]},"department":[{"_id":"KrCh"}],"month":"10","publisher":"Springer","day":"01","oa":1,"corr_author":"1","fulldoi":"https://doi.org/10.1007/978-3-642-33090-2_27","das_tickbox":"1","arxiv":1,"main_file_link":[{"url":"https://arxiv.org/abs/1604.08234","open_access":"1"}],"date_published":"2012-10-01T00:00:00Z","alternative_title":["LNCS"],"conference":{"name":"ESA: European Symposium on Algorithms","end_date":"2012-09-12","start_date":"2012-09-10","location":"Ljubljana, Slovenia"},"article_processing_charge":"No","quality_controlled":"1","year":"2012","publication_status":"published","intvolume":"      7501"},{"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory","grant_number":"S11407"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"page":"115-131","citation":{"mla":"Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” <i>CONCUR 2012 - Concurrency Theory</i>, edited by Maciej Koutny and Irek Ulidowski, vol. 7454, Springer, 2012, pp. 115–31, doi:<a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">10.1007/978-3-642-32940-1_10</a>.","ama":"Chatterjee K, Randour M, Raskin J-F. Strategy synthesis for multi-dimensional quantitative objectives. In: Koutny M, Ulidowski I, eds. <i>CONCUR 2012 - Concurrency Theory</i>. Vol 7454. Berlin, Heidelberg: Springer; 2012:115-131. doi:<a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">10.1007/978-3-642-32940-1_10</a>","short":"K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.), CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.","ieee":"K. Chatterjee, M. Randour, and J.-F. Raskin, “Strategy synthesis for multi-dimensional quantitative objectives,” in <i>CONCUR 2012 - Concurrency Theory</i>, Newcastle upon Tyne, United Kingdom, 2012, vol. 7454, pp. 115–131.","ista":"Chatterjee K, Randour M, Raskin J-F. 2012. Strategy synthesis for multi-dimensional quantitative objectives. CONCUR 2012 - Concurrency Theory. CONCUR: Conference on Concurrency Theory, LNCS, vol. 7454, 115–131.","chicago":"Chatterjee, Krishnendu, Mickael Randour, and Jean-François Raskin. “Strategy Synthesis for Multi-Dimensional Quantitative Objectives.” In <i>CONCUR 2012 - Concurrency Theory</i>, edited by Maciej Koutny and Irek Ulidowski, 7454:115–31. Berlin, Heidelberg: Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">https://doi.org/10.1007/978-3-642-32940-1_10</a>.","apa":"Chatterjee, K., Randour, M., &#38; Raskin, J.-F. (2012). Strategy synthesis for multi-dimensional quantitative objectives. In M. Koutny &#38; I. Ulidowski (Eds.), <i>CONCUR 2012 - Concurrency Theory</i> (Vol. 7454, pp. 115–131). Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-642-32940-1_10\">https://doi.org/10.1007/978-3-642-32940-1_10</a>"},"related_material":{"record":[{"relation":"later_version","id":"2716","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-07-28T11:24:51Z","date_created":"2022-03-21T08:00:21Z","status":"public","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Randour","first_name":"Mickael","full_name":"Randour, Mickael"},{"first_name":"Jean-François","last_name":"Raskin","full_name":"Raskin, Jean-François"}],"_id":"10904","title":"Strategy synthesis for multi-dimensional quantitative objectives","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 VASS (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."}],"type":"conference","oa_version":"Preprint","OA_type":"green","OA_place":"repository","language":[{"iso":"eng"}],"scopus_import":"1","publication":"CONCUR 2012 - Concurrency Theory","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783642329401"],"isbn":["9783642329395"]},"acknowledgement":"Author supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407 (RiSE), ERC Start Grant (279307: Graph Games), Microsoft faculty fellowship.","ec_funded":1,"article_processing_charge":"No","date_published":"2012-09-15T00:00:00Z","alternative_title":["LNCS"],"conference":{"start_date":"2012-09-04","end_date":"2012-09-07","name":"CONCUR: Conference on Concurrency Theory","location":"Newcastle upon Tyne, United Kingdom"},"arxiv":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1201.5073"}],"fulldoi":"https://doi.org/10.1007/978-3-642-32940-1_10","place":"Berlin, Heidelberg","editor":[{"last_name":"Koutny","first_name":"Maciej","full_name":"Koutny, Maciej"},{"first_name":"Irek","last_name":"Ulidowski","full_name":"Ulidowski, Irek"}],"intvolume":"      7454","year":"2012","quality_controlled":"1","publication_status":"published","doi":"10.1007/978-3-642-32940-1_10","volume":7454,"corr_author":"1","oa":1,"day":"15","department":[{"_id":"KrCh"}],"month":"09","publisher":"Springer","external_id":{"arxiv":["1201.5073"]}},{"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"1400"}]},"citation":{"apa":"Diaz Jr, L., Williams, R., Wu, J., Kinde, I., Hecht, J., Berlin, J., … Vogelstein, B. (2012). The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers. <i>Nature</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nature11219\">https://doi.org/10.1038/nature11219</a>","chicago":"Diaz Jr, Luis, Richard Williams, Jian Wu, Isaac Kinde, Joel Hecht, Jordan Berlin, Benjamin Allen, et al. “The Molecular Evolution of Acquired Resistance to Targeted EGFR Blockade in Colorectal Cancers.” <i>Nature</i>. Nature Publishing Group, 2012. <a href=\"https://doi.org/10.1038/nature11219\">https://doi.org/10.1038/nature11219</a>.","ista":"Diaz Jr L, Williams R, Wu J, Kinde I, Hecht J, Berlin J, Allen B, Božić I, Reiter J, Nowak M, Kinzler K, Oliner K, Vogelstein B. 2012. The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers. Nature. 486(7404), 537–540.","short":"L. Diaz Jr, R. Williams, J. Wu, I. Kinde, J. Hecht, J. Berlin, B. Allen, I. Božić, J. Reiter, M. Nowak, K. Kinzler, K. Oliner, B. Vogelstein, Nature 486 (2012) 537–540.","ieee":"L. Diaz Jr <i>et al.</i>, “The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers,” <i>Nature</i>, vol. 486, no. 7404. Nature Publishing Group, pp. 537–540, 2012.","ama":"Diaz Jr L, Williams R, Wu J, et al. The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers. <i>Nature</i>. 2012;486(7404):537-540. doi:<a href=\"https://doi.org/10.1038/nature11219\">10.1038/nature11219</a>","mla":"Diaz Jr, Luis, et al. “The Molecular Evolution of Acquired Resistance to Targeted EGFR Blockade in Colorectal Cancers.” <i>Nature</i>, vol. 486, no. 7404, Nature Publishing Group, 2012, pp. 537–40, doi:<a href=\"https://doi.org/10.1038/nature11219\">10.1038/nature11219</a>."},"page":"537 - 540","project":[{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23"}],"date_updated":"2026-07-29T10:15:25Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers","_id":"3157","status":"public","date_created":"2018-12-11T12:01:43Z","author":[{"full_name":"Diaz Jr, Luis","last_name":"Diaz Jr","first_name":"Luis"},{"first_name":"Richard","last_name":"Williams","full_name":"Williams, Richard"},{"full_name":"Wu, Jian","last_name":"Wu","first_name":"Jian"},{"full_name":"Kinde, Isaac","first_name":"Isaac","last_name":"Kinde"},{"full_name":"Hecht, Joel","last_name":"Hecht","first_name":"Joel"},{"last_name":"Berlin","first_name":"Jordan","full_name":"Berlin, Jordan"},{"full_name":"Allen, Benjamin","first_name":"Benjamin","last_name":"Allen"},{"full_name":"Božić, Ivana","first_name":"Ivana","last_name":"Božić"},{"first_name":"Johannes","last_name":"Reiter","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"},{"full_name":"Kinzler, Kenneth","last_name":"Kinzler","first_name":"Kenneth"},{"full_name":"Oliner, Kelly","last_name":"Oliner","first_name":"Kelly"},{"last_name":"Vogelstein","first_name":"Bert","full_name":"Vogelstein, Bert"}],"oa_version":"Submitted Version","type":"journal_article","abstract":[{"text":"Colorectal tumours that are wild type for KRAS are often sensitive to EGFR blockade, but almost always develop resistance within several months of initiating therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies are largely unknown. This situation is in marked contrast to that of small-molecule targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations in the genes encoding the protein targets render the tumours resistant to the effects of the drugs. The simplest hypothesis to account for the development of resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis would seem readily testable, there is no evidence in pre-clinical models to support it, nor is there data from patients. To test this hypothesis, we determined whether mutant KRAS DNA could be detected in the circulation of 28 patients receiving monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that 9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed detectable mutations in KRAS in their sera, three of which developed multiple different KRAS mutations. The appearance of these mutations was very consistent, generally occurring between 5 and 6months following treatment. Mathematical modelling indicated that the mutations were present in expanded subclones before the initiation of panitumumab treatment. These results suggest that the emergence of KRAS mutations is a mediator of acquired resistance to EGFR blockade and that these mutations can be detected in a non-invasive manner. They explain why solid tumours develop resistance to targeted therapies in a highly reproducible fashion.","lang":"eng"}],"language":[{"iso":"eng"}],"publist_id":"3537","publication":"Nature","scopus_import":"1","issue":"7404","ec_funded":1,"date_published":"2012-06-28T00:00:00Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.1038/nature11219","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3436069/","open_access":"1"}],"publication_status":"published","year":"2012","quality_controlled":"1","pmid":1,"intvolume":"       486","isi":1,"volume":486,"doi":"10.1038/nature11219","day":"28","oa":1,"external_id":{"pmid":["22722843"],"isi":["000305760600044"]},"publisher":"Nature Publishing Group","department":[{"_id":"KrCh"}],"month":"06"},{"ec_funded":1,"issue":"1","scopus_import":"1","publication":"Theoretical Population Biology","publist_id":"3388","language":[{"iso":"eng"}],"abstract":[{"text":"Many scenarios in the living world, where individual organisms compete for winning positions (or resources), have properties of auctions. Here we study the evolution of bids in biological auctions. For each auction, n individuals are drawn at random from a population of size N. Each individual makes a bid which entails a cost. The winner obtains a benefit of a certain value. Costs and benefits are translated into reproductive success (fitness). Therefore, successful bidding strategies spread in the population. We compare two types of auctions. In “biological all-pay auctions”, the costs are the bid for every participating individual. In “biological second price all-pay auctions”, the cost for everyone other than the winner is the bid, but the cost for the winner is the second highest bid. Second price all-pay auctions are generalizations of the “war of attrition” introduced by Maynard Smith. We study evolutionary dynamics in both types of auctions. We calculate pairwise invasion plots and evolutionarily stable distributions over the continuous strategy space. We find that the average bid in second price all-pay auctions is higher than in all-pay auctions, but the average cost for the winner is similar in both auctions. In both cases, the average bid is a declining function of the number of participants, n. The more individuals participate in an auction the smaller is the chance of winning, and thus expensive bids must be avoided.\r\n","lang":"eng"}],"oa_version":"Submitted Version","type":"journal_article","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes","last_name":"Reiter","first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"status":"public","date_created":"2018-12-11T12:02:19Z","_id":"3260","title":"Evolutionary dynamics of biological auctions","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2026-07-29T10:15:25Z","project":[{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23"},{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"citation":{"apa":"Chatterjee, K., Reiter, J., &#38; Nowak, M. (2012). Evolutionary dynamics of biological auctions. <i>Theoretical Population Biology</i>. Academic Press. <a href=\"https://doi.org/10.1016/j.tpb.2011.11.003\">https://doi.org/10.1016/j.tpb.2011.11.003</a>","chicago":"Chatterjee, Krishnendu, Johannes Reiter, and Martin Nowak. “Evolutionary Dynamics of Biological Auctions.” <i>Theoretical Population Biology</i>. Academic Press, 2012. <a href=\"https://doi.org/10.1016/j.tpb.2011.11.003\">https://doi.org/10.1016/j.tpb.2011.11.003</a>.","ieee":"K. Chatterjee, J. Reiter, and M. Nowak, “Evolutionary dynamics of biological auctions,” <i>Theoretical Population Biology</i>, vol. 81, no. 1. Academic Press, pp. 69–80, 2012.","short":"K. Chatterjee, J. Reiter, M. Nowak, Theoretical Population Biology 81 (2012) 69–80.","ista":"Chatterjee K, Reiter J, Nowak M. 2012. Evolutionary dynamics of biological auctions. Theoretical Population Biology. 81(1), 69–80.","mla":"Chatterjee, Krishnendu, et al. “Evolutionary Dynamics of Biological Auctions.” <i>Theoretical Population Biology</i>, vol. 81, no. 1, Academic Press, 2012, pp. 69–80, doi:<a href=\"https://doi.org/10.1016/j.tpb.2011.11.003\">10.1016/j.tpb.2011.11.003</a>.","ama":"Chatterjee K, Reiter J, Nowak M. Evolutionary dynamics of biological auctions. <i>Theoretical Population Biology</i>. 2012;81(1):69-80. doi:<a href=\"https://doi.org/10.1016/j.tpb.2011.11.003\">10.1016/j.tpb.2011.11.003</a>"},"page":"69 - 80","related_material":{"record":[{"status":"public","id":"1400","relation":"dissertation_contains"}]},"month":"02","department":[{"_id":"KrCh"}],"publisher":"Academic Press","external_id":{"pmid":["22120126"],"isi":["000298938200006"]},"oa":1,"corr_author":"1","day":"01","doi":"10.1016/j.tpb.2011.11.003","volume":81,"isi":1,"intvolume":"        81","pmid":1,"year":"2012","quality_controlled":"1","publication_status":"published","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3279759/ ","open_access":"1"}],"fulldoi":"https://doi.org/10.1016/j.tpb.2011.11.003","article_processing_charge":"No","date_published":"2012-02-01T00:00:00Z"},{"date_updated":"2026-08-12T14:34:15Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Finite Automata with Time Delay Blocks.” In <i>Proceedings of the 10th ACM International Conference on Embedded Software</i>, 43–52. ACM, 2012. <a href=\"https://doi.org/10.1145/2380356.2380370\">https://doi.org/10.1145/2380356.2380370</a>.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Prabhu, V. (2012). Finite automata with time delay blocks. In <i>Proceedings of the 10th ACM international conference on Embedded software</i> (pp. 43–52). Tampere, Finland: ACM. <a href=\"https://doi.org/10.1145/2380356.2380370\">https://doi.org/10.1145/2380356.2380370</a>","ama":"Chatterjee K, Henzinger TA, Prabhu V. Finite automata with time delay blocks. In: <i>Proceedings of the 10th ACM International Conference on Embedded Software</i>. ACM; 2012:43-52. doi:<a href=\"https://doi.org/10.1145/2380356.2380370\">10.1145/2380356.2380370</a>","mla":"Chatterjee, Krishnendu, et al. “Finite Automata with Time Delay Blocks.” <i>Proceedings of the 10th ACM International Conference on Embedded Software</i>, ACM, 2012, pp. 43–52, doi:<a href=\"https://doi.org/10.1145/2380356.2380370\">10.1145/2380356.2380370</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Finite automata with time delay blocks,” in <i>Proceedings of the 10th ACM international conference on Embedded software</i>, Tampere, Finland, 2012, pp. 43–52.","ista":"Chatterjee K, Henzinger TA, Prabhu V. 2012. Finite automata with time delay blocks. Proceedings of the 10th ACM international conference on Embedded software. EMSOFT: Embedded Software , 43–52.","short":"K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Proceedings of the 10th ACM International Conference on Embedded Software, ACM, 2012, pp. 43–52."},"page":"43 - 52","project":[{"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 Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","type":"conference","abstract":[{"text":"The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce automata with delay blocks (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete. Copyright 2012 ACM.","lang":"eng"}],"title":"Finite automata with time delay blocks","_id":"2936","date_created":"2018-12-11T12:00:26Z","status":"public","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"first_name":"Vinayak","last_name":"Prabhu","full_name":"Prabhu, Vinayak"}],"publist_id":"3799","language":[{"iso":"eng"}],"acknowledgement":"This work has been financially supported in part by the European Commission FP7-ICT Cognitive Systems, Interaction, and Robotics under the contract # 270180 (NOPTILUS); by Fundacao para Ciencia e Tecnologia under project PTDC/EEA-CRO/104901/2008 (Modeling and control of Networked vehicle systems in persistent autonomous operations); by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification; FWF NFN Grant No S11407-N23 (RiSE); ERC Start grant (279307: Graph Games); Microsoft faculty fellows award; ERC Advanced grant QUAREM; and FWF Grant No S11403-N23 (RiSE).","ec_funded":1,"publication":"Proceedings of the 10th ACM international conference on Embedded software","scopus_import":"1","fulldoi":"https://doi.org/10.1145/2380356.2380370","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1207.7019"}],"arxiv":1,"conference":{"name":"EMSOFT: Embedded Software ","end_date":"2012-10-12","start_date":"2012-10-07","location":"Tampere, Finland"},"date_published":"2012-10-01T00:00:00Z","article_processing_charge":"No","publication_status":"published","quality_controlled":"1","year":"2012","doi":"10.1145/2380356.2380370","external_id":{"arxiv":["1207.7019"]},"publisher":"ACM","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"month":"10","day":"01","oa":1},{"citation":{"ieee":"K. Chatterjee and M. Henzinger, <i>An O(n2) time algorithm for alternating Büchi games</i>. IST Austria, 2011.","ista":"Chatterjee K, Henzinger M. 2011. An O(n2) time algorithm for alternating Büchi games, IST Austria, 20p.","short":"K. Chatterjee, M. Henzinger, An O(N2) Time Algorithm for Alternating Büchi Games, IST Austria, 2011.","mla":"Chatterjee, Krishnendu, and Monika Henzinger. <i>An O(N2) Time Algorithm for Alternating Büchi Games</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">10.15479/AT:IST-2011-0009</a>.","ama":"Chatterjee K, Henzinger M. <i>An O(N2) Time Algorithm for Alternating Büchi Games</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">10.15479/AT:IST-2011-0009</a>","apa":"Chatterjee, K., &#38; Henzinger, M. (2011). <i>An O(n2) time algorithm for alternating Büchi games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">https://doi.org/10.15479/AT:IST-2011-0009</a>","chicago":"Chatterjee, Krishnendu, and Monika Henzinger. <i>An O(N2) Time Algorithm for Alternating Büchi Games</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0009\">https://doi.org/10.15479/AT:IST-2011-0009</a>."},"page":"20","related_material":{"record":[{"status":"public","id":"3165","relation":"later_version"}]},"date_updated":"2025-07-10T11:52:28Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"}],"date_created":"2018-12-12T11:38:59Z","title":"An O(n2) time algorithm for alternating Büchi games","_id":"5379","abstract":[{"text":"Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is ̃O(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the ̃O(n·m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3 an earlier bound of O(min(m1.5, m·n2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.","lang":"eng"}],"oa_version":"Published Version","type":"technical_report","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"article_processing_charge":"No","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:39Z","date_published":"2011-07-11T00:00:00Z","fulldoi":"https://doi.org/10.15479/AT:IST-2011-0009","ddc":["000","004"],"publication_status":"published","year":"2011","doi":"10.15479/AT:IST-2011-0009","file":[{"file_id":"5504","file_size":388665,"content_type":"application/pdf","date_updated":"2020-07-14T12:46:39Z","file_name":"IST-2011-0009_IST-2011-0009.pdf","checksum":"0b354264229045d982332fd2cb5b9a26","date_created":"2018-12-12T11:53:43Z","relation":"main_file","creator":"system","access_level":"open_access"}],"oa":1,"pubrep_id":"15","day":"11","publisher":"IST Austria","department":[{"_id":"KrCh"}],"month":"07"},{"publisher":"IST Austria","department":[{"_id":"KrCh"}],"month":"07","day":"11","oa":1,"pubrep_id":"16","doi":"10.15479/AT:IST-2011-0008","file":[{"date_created":"2018-12-12T11:54:22Z","checksum":"0fd38186409be819a911c4990fa79d1f","relation":"main_file","creator":"system","access_level":"open_access","file_id":"5544","file_size":500399,"date_updated":"2020-07-14T12:46:39Z","content_type":"application/pdf","file_name":"IST-2011-0008_IST-2011-0008.pdf"}],"publication_status":"published","year":"2011","ddc":["000"],"fulldoi":"https://doi.org/10.15479/AT:IST-2011-0008","has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:39Z","date_published":"2011-07-11T00:00:00Z","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"type":"technical_report","oa_version":"Published Version","abstract":[{"text":"We consider 2-player games played on a finite state space for an infinite number of rounds.  The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We study concurrent games with ω-regular winning conditions specified as parity objectives.  We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies.  In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite-precision;  and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies.  We show that the winning sets can be computed in O(n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms,that are obtained by characterization of the winning sets as μ-calculus formulas, are considerably more involved than those for turn-based games.","lang":"eng"}],"title":"Bounded rationality in concurrent parity games","_id":"5380","date_created":"2018-12-12T11:39:00Z","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"status":"public","date_updated":"2025-06-26T09:28:52Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"3338","relation":"later_version"}]},"citation":{"apa":"Chatterjee, K. (2011). <i>Bounded rationality in concurrent parity games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">https://doi.org/10.15479/AT:IST-2011-0008</a>","chicago":"Chatterjee, Krishnendu. <i>Bounded Rationality in Concurrent Parity Games</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">https://doi.org/10.15479/AT:IST-2011-0008</a>.","short":"K. Chatterjee, Bounded Rationality in Concurrent Parity Games, IST Austria, 2011.","ieee":"K. Chatterjee, <i>Bounded rationality in concurrent parity games</i>. IST Austria, 2011.","ista":"Chatterjee K. 2011. Bounded rationality in concurrent parity games, IST Austria, 53p.","mla":"Chatterjee, Krishnendu. <i>Bounded Rationality in Concurrent Parity Games</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">10.15479/AT:IST-2011-0008</a>.","ama":"Chatterjee K. <i>Bounded Rationality in Concurrent Parity Games</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0008\">10.15479/AT:IST-2011-0008</a>"},"page":"53"},{"month":"06","department":[{"_id":"KrCh"}],"publisher":"IST Austria","day":"27","pubrep_id":"18","oa":1,"file":[{"date_created":"2018-12-12T11:54:24Z","checksum":"1322b652d6ab07eb5248298a3f91c1cf","creator":"system","relation":"main_file","access_level":"open_access","file_id":"5546","file_size":335997,"file_name":"IST-2011-0006_IST-2011-0006.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:40Z"}],"doi":"10.15479/AT:IST-2011-0006","year":"2011","publication_status":"published","ddc":["000","005"],"fulldoi":"https://doi.org/10.15479/AT:IST-2011-0006","file_date_updated":"2020-07-14T12:46:40Z","date_published":"2011-06-27T00:00:00Z","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"type":"technical_report","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We consider two-player stochastic games played on a finite state space for an infinite num- ber of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with ω-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity games with respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition func- tion is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal)."}],"_id":"5382","title":"Robustness of structurally equivalent concurrent parity games","status":"public","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"}],"date_created":"2018-12-12T11:39:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-04-15T08:12:24Z","related_material":{"record":[{"relation":"later_version","id":"3341","status":"public"}]},"page":"18","citation":{"chicago":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">https://doi.org/10.15479/AT:IST-2011-0006</a>.","apa":"Chatterjee, K. (2011). <i>Robustness of structurally equivalent concurrent parity games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">https://doi.org/10.15479/AT:IST-2011-0006</a>","ama":"Chatterjee K. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">10.15479/AT:IST-2011-0006</a>","mla":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0006\">10.15479/AT:IST-2011-0006</a>.","ieee":"K. Chatterjee, <i>Robustness of structurally equivalent concurrent parity games</i>. IST Austria, 2011.","short":"K. Chatterjee, Robustness of Structurally Equivalent Concurrent Parity Games, IST Austria, 2011.","ista":"Chatterjee K. 2011. Robustness of structurally equivalent concurrent parity games, IST Austria, 18p."}},{"publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"title":"Decidable problems for probabilistic automata on infinite words","_id":"5384","status":"public","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Tracol, Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","last_name":"Tracol","first_name":"Mathieu"}],"date_created":"2018-12-12T11:39:01Z","type":"technical_report","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every ε > 0 there is a word that is accepted with probability at least 1 − ε. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions."}],"related_material":{"record":[{"id":"2957","relation":"later_version","status":"public"}]},"page":"30","citation":{"apa":"Chatterjee, K., &#38; Tracol, M. (2011). <i>Decidable problems for probabilistic automata on infinite words</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">https://doi.org/10.15479/AT:IST-2011-0004</a>","chicago":"Chatterjee, Krishnendu, and Mathieu Tracol. <i>Decidable Problems for Probabilistic Automata on Infinite Words</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">https://doi.org/10.15479/AT:IST-2011-0004</a>.","ista":"Chatterjee K, Tracol M. 2011. Decidable problems for probabilistic automata on infinite words, IST Austria, 30p.","short":"K. Chatterjee, M. Tracol, Decidable Problems for Probabilistic Automata on Infinite Words, IST Austria, 2011.","ieee":"K. Chatterjee and M. Tracol, <i>Decidable problems for probabilistic automata on infinite words</i>. IST Austria, 2011.","ama":"Chatterjee K, Tracol M. <i>Decidable Problems for Probabilistic Automata on Infinite Words</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">10.15479/AT:IST-2011-0004</a>","mla":"Chatterjee, Krishnendu, and Mathieu Tracol. <i>Decidable Problems for Probabilistic Automata on Infinite Words</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0004\">10.15479/AT:IST-2011-0004</a>."},"date_updated":"2025-09-30T08:07:38Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"11","oa":1,"corr_author":"1","pubrep_id":"20","publisher":"IST Austria","month":"04","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2011-0004","file":[{"file_id":"5545","file_name":"IST-2011-004_IST-2011-0004.pdf","date_updated":"2020-07-14T12:46:40Z","content_type":"application/pdf","file_size":570827,"checksum":"f5a0f664fadc335990f5fcf138df19f1","date_created":"2018-12-12T11:54:23Z","access_level":"open_access","relation":"main_file","creator":"system"}],"ddc":["000","005"],"publication_status":"published","year":"2011","has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:40Z","alternative_title":["IST Austria Technical Report"],"date_published":"2011-04-11T00:00:00Z","fulldoi":"https://doi.org/10.15479/AT:IST-2011-0004"},{"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-04-15T08:12:14Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"3345"}]},"citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Energy and Mean-Payoff Parity Markov Decision Processes</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">https://doi.org/10.15479/AT:IST-2011-0001</a>.","apa":"Chatterjee, K., &#38; Doyen, L. (2011). <i>Energy and mean-payoff parity Markov decision processes</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">https://doi.org/10.15479/AT:IST-2011-0001</a>","ama":"Chatterjee K, Doyen L. <i>Energy and Mean-Payoff Parity Markov Decision Processes</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">10.15479/AT:IST-2011-0001</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Energy and Mean-Payoff Parity Markov Decision Processes</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0001\">10.15479/AT:IST-2011-0001</a>.","ista":"Chatterjee K, Doyen L. 2011. Energy and mean-payoff parity Markov decision processes, IST Austria, 20p.","short":"K. Chatterjee, L. Doyen, Energy and Mean-Payoff Parity Markov Decision Processes, IST Austria, 2011.","ieee":"K. Chatterjee and L. Doyen, <i>Energy and mean-payoff parity Markov decision processes</i>. IST Austria, 2011."},"page":"20","type":"technical_report","oa_version":"Published Version","abstract":[{"text":"We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.","lang":"eng"}],"_id":"5387","title":"Energy and mean-payoff parity Markov decision processes","date_created":"2018-12-12T11:39:02Z","status":"public","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"}],"file":[{"access_level":"open_access","relation":"main_file","creator":"system","checksum":"824d6c70e6d3feb3e836b009e0b3cf73","date_created":"2018-12-12T11:52:57Z","date_updated":"2020-07-14T12:46:41Z","content_type":"application/pdf","file_name":"IST-2011-0001_IST-2011-0001.pdf","file_size":329976,"file_id":"5458"}],"doi":"10.15479/AT:IST-2011-0001","month":"02","department":[{"_id":"KrCh"}],"publisher":"IST Austria","day":"16","pubrep_id":"23","oa":1,"fulldoi":"https://doi.org/10.15479/AT:IST-2011-0001","file_date_updated":"2020-07-14T12:46:41Z","alternative_title":["IST Austria Technical Report"],"date_published":"2011-02-16T00:00:00Z","has_accepted_license":"1","year":"2011","publication_status":"published","ddc":["000","005"]}]