[{"page":"210 - 225","type":"conference","ec_funded":1,"year":"2014","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2014-04-01T00:00:00Z","alternative_title":["LNCS"],"date_created":"2018-12-11T11:56:21Z","abstract":[{"lang":"eng","text":"The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2 1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2 1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic). We present an algorithm running in time O(d·n2d·MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2 1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective). "}],"publisher":"Springer","language":[{"iso":"eng"}],"intvolume":"      8412","month":"04","status":"public","acknowledgement":"This research was supported by European project Cassting (FP7-601148).\r\nA Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/128.","related_material":{"record":[{"id":"5405","relation":"earlier_version","status":"public"}]},"day":"01","conference":{"end_date":"2014-04-13","location":"Grenoble, France","name":"FoSSaCS: Foundations of Software Science and Computation Structures","start_date":"2014-04-05"},"author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"full_name":"Gimbert, Hugo","first_name":"Hugo","last_name":"Gimbert"},{"full_name":"Oualhadj, Youssouf","first_name":"Youssouf","last_name":"Oualhadj"}],"date_updated":"2023-02-23T12:24:50Z","title":"Perfect-information stochastic mean-payoff parity games","department":[{"_id":"KrCh"}],"scopus_import":1,"volume":8412,"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"doi":"10.1007/978-3-642-54830-7_14","citation":{"short":"K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, in:, Springer, 2014, pp. 210–225.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. “Perfect-Information Stochastic Mean-Payoff Parity Games,” 8412:210–25. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">https://doi.org/10.1007/978-3-642-54830-7_14</a>.","ista":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2014. Perfect-information stochastic mean-payoff parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 210–225.","apa":"Chatterjee, K., Doyen, L., Gimbert, H., &#38; Oualhadj, Y. (2014). Perfect-information stochastic mean-payoff parity games (Vol. 8412, pp. 210–225). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">https://doi.org/10.1007/978-3-642-54830-7_14</a>","ama":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-information stochastic mean-payoff parity games. In: Vol 8412. Springer; 2014:210-225. doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">10.1007/978-3-642-54830-7_14</a>","mla":"Chatterjee, Krishnendu, et al. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. Vol. 8412, Springer, 2014, pp. 210–25, doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_14\">10.1007/978-3-642-54830-7_14</a>.","ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, “Perfect-information stochastic mean-payoff parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 210–225."},"publist_id":"4758","_id":"2212","oa_version":"None","quality_controlled":"1"},{"author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"},{"first_name":"Sumit","last_name":"Nain","full_name":"Nain, Sumit"},{"full_name":"Vardi, Moshe","first_name":"Moshe","last_name":"Vardi"}],"title":"The complexity of partial-observation stochastic parity games with finite-memory strategies","date_updated":"2023-02-23T12:24:58Z","arxiv":1,"day":"01","acknowledgement":"This research was supported by European project Cassting (FP7-601148), NSF grants CNS 1049862 and CCF-1139011, by NSF Expe ditions in Computing project “ExCAPE: Expeditions in Computer Augmented Program Engineering”, by BSF grant 9800096, and by gift from Intel.","related_material":{"record":[{"relation":"earlier_version","id":"5408","status":"public"}]},"external_id":{"arxiv":["1401.3289"]},"conference":{"end_date":"2014-04-13","name":"FoSSaCS: Foundations of Software Science and Computation Structures","location":"Grenoble, France","start_date":"2014-04-05"},"quality_controlled":"1","oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/1401.3289","open_access":"1"}],"_id":"2213","publist_id":"4757","volume":8412,"department":[{"_id":"KrCh"}],"scopus_import":1,"citation":{"apa":"Chatterjee, K., Doyen, L., Nain, S., &#38; Vardi, M. (2014). The complexity of partial-observation stochastic parity games with finite-memory strategies (Vol. 8412, pp. 242–257). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">https://doi.org/10.1007/978-3-642-54830-7_16</a>","ista":"Chatterjee K, Doyen L, Nain S, Vardi M. 2014. The complexity of partial-observation stochastic parity games with finite-memory strategies. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 242–257.","ama":"Chatterjee K, Doyen L, Nain S, Vardi M. The complexity of partial-observation stochastic parity games with finite-memory strategies. In: Vol 8412. Springer; 2014:242-257. doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">10.1007/978-3-642-54830-7_16</a>","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies</i>. Vol. 8412, Springer, 2014, pp. 242–57, doi:<a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">10.1007/978-3-642-54830-7_16</a>.","ieee":"K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, “The complexity of partial-observation stochastic parity games with finite-memory strategies,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 242–257.","short":"K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. “The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies,” 8412:242–57. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54830-7_16\">https://doi.org/10.1007/978-3-642-54830-7_16</a>."},"doi":"10.1007/978-3-642-54830-7_16","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","year":"2014","date_published":"2014-04-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"242 - 257","oa":1,"type":"conference","ec_funded":1,"month":"04","status":"public","publisher":"Springer","abstract":[{"text":"We consider two-player partial-observation stochastic games on finitestate graphs where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are ε-regular conditions specified as parity objectives. The qualitative-analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). These qualitative-analysis problems are known to be undecidable. However in many applications the relevant question is the existence of finite-memory strategies, and the qualitative-analysis problems under finite-memory strategies was recently shown to be decidable in 2EXPTIME.We improve the complexity and show that the qualitative-analysis problems for partial-observation stochastic parity games under finite-memory strategies are EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis.","lang":"eng"}],"date_created":"2018-12-11T11:56:21Z","alternative_title":["LNCS"],"intvolume":"      8412","language":[{"iso":"eng"}]},{"page":"303 - 312","related_material":{"record":[{"relation":"earlier_version","id":"5409","status":"public"}]},"day":"01","oa":1,"type":"conference","conference":{"start_date":"2017-04-15","location":"Berlin, Germany","name":"HSCC: Hybrid Systems - Computation and Control","end_date":"2017-04-17"},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"},{"first_name":"Ritankar","last_name":"Majumdar","full_name":"Majumdar, Ritankar"}],"year":"2014","publication_status":"published","date_updated":"2024-10-21T06:02:53Z","date_published":"2014-01-01T00:00:00Z","title":"Edit distance for timed automata","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T11:56:22Z","abstract":[{"text":"The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in time stamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than δ away from the parameter, for δ &gt; 0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and analogous decidability results hold for rectangular automata.","lang":"eng"}],"scopus_import":"1","doi":"10.1145/2562059.2562141","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Majumdar, R. (2014). Edit distance for timed automata (pp. 303–312). Presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany: Springer. <a href=\"https://doi.org/10.1145/2562059.2562141\">https://doi.org/10.1145/2562059.2562141</a>","ista":"Chatterjee K, Ibsen-Jensen R, Majumdar R. 2014. Edit distance for timed automata. HSCC: Hybrid Systems - Computation and Control, 303–312.","ama":"Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit distance for timed automata. In: Springer; 2014:303-312. doi:<a href=\"https://doi.org/10.1145/2562059.2562141\">10.1145/2562059.2562141</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, “Edit distance for timed automata,” presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany, 2014, pp. 303–312.","mla":"Chatterjee, Krishnendu, et al. <i>Edit Distance for Timed Automata</i>. Springer, 2014, pp. 303–12, doi:<a href=\"https://doi.org/10.1145/2562059.2562141\">10.1145/2562059.2562141</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, in:, Springer, 2014, pp. 303–312.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Ritankar Majumdar. “Edit Distance for Timed Automata,” 303–12. Springer, 2014. <a href=\"https://doi.org/10.1145/2562059.2562141\">https://doi.org/10.1145/2562059.2562141</a>."},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://dl.acm.org/citation.cfm?doid=2562059.2562141"}],"month":"01","status":"public","oa_version":"Submitted Version","quality_controlled":"1","publist_id":"4752","_id":"2216"},{"citation":{"mla":"Grinshpun, Andrey, et al. “Alternating Traps in Muller and Parity Games.” <i>Theoretical Computer Science</i>, vol. 521, Elsevier, 2014, pp. 73–91, doi:<a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">10.1016/j.tcs.2013.11.032</a>.","ieee":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, and A. Tarfulea, “Alternating traps in Muller and parity games,” <i>Theoretical Computer Science</i>, vol. 521. Elsevier, pp. 73–91, 2014.","ama":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. Alternating traps in Muller and parity games. <i>Theoretical Computer Science</i>. 2014;521:73-91. doi:<a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">10.1016/j.tcs.2013.11.032</a>","apa":"Grinshpun, A., Phalitnonkiat, P., Rubin, S., &#38; Tarfulea, A. (2014). Alternating traps in Muller and parity games. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">https://doi.org/10.1016/j.tcs.2013.11.032</a>","ista":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. 2014. Alternating traps in Muller and parity games. Theoretical Computer Science. 521, 73–91.","chicago":"Grinshpun, Andrey, Pakawat Phalitnonkiat, Sasha Rubin, and Andrei Tarfulea. “Alternating Traps in Muller and Parity Games.” <i>Theoretical Computer Science</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tcs.2013.11.032\">https://doi.org/10.1016/j.tcs.2013.11.032</a>.","short":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, A. Tarfulea, Theoretical Computer Science 521 (2014) 73–91."},"doi":"10.1016/j.tcs.2013.11.032","scopus_import":"1","department":[{"_id":"KrCh"}],"volume":521,"_id":"2246","publist_id":"4703","quality_controlled":"1","oa_version":"Submitted Version","main_file_link":[{"url":"http://arxiv.org/abs/1303.3777","open_access":"1"}],"external_id":{"arxiv":["1303.3777"],"isi":["000331433100007"]},"day":"13","publication_identifier":{"issn":["0304-3975"]},"arxiv":1,"title":"Alternating traps in Muller and parity games","date_updated":"2026-04-16T10:08:15Z","author":[{"last_name":"Grinshpun","first_name":"Andrey","full_name":"Grinshpun, Andrey"},{"first_name":"Pakawat","last_name":"Phalitnonkiat","full_name":"Phalitnonkiat, Pakawat"},{"full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","last_name":"Rubin","first_name":"Sasha"},{"full_name":"Tarfulea, Andrei","last_name":"Tarfulea","first_name":"Andrei"}],"language":[{"iso":"eng"}],"intvolume":"       521","abstract":[{"lang":"eng","text":"Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. "}],"date_created":"2018-12-11T11:56:33Z","publisher":"Elsevier","month":"02","corr_author":"1","status":"public","publication":"Theoretical Computer Science","type":"journal_article","isi":1,"oa":1,"page":"73 - 91","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","date_published":"2014-02-13T00:00:00Z","publication_status":"published","article_processing_charge":"No","year":"2014"},{"volume":61,"department":[{"_id":"KrCh"}],"scopus_import":"1","doi":"10.1145/2597631","citation":{"short":"K. Chatterjee, M. Henzinger, Journal of the ACM 61 (2014).","chicago":"Chatterjee, Krishnendu, and Monika Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” <i>Journal of the ACM</i>. ACM, 2014. <a href=\"https://doi.org/10.1145/2597631\">https://doi.org/10.1145/2597631</a>.","ista":"Chatterjee K, Henzinger M. 2014. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 61(3), a15.","ama":"Chatterjee K, Henzinger M. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. <i>Journal of the ACM</i>. 2014;61(3). doi:<a href=\"https://doi.org/10.1145/2597631\">10.1145/2597631</a>","apa":"Chatterjee, K., &#38; Henzinger, M. (2014). Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/2597631\">https://doi.org/10.1145/2597631</a>","mla":"Chatterjee, Krishnendu, and Monika Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” <i>Journal of the ACM</i>, vol. 61, no. 3, a15, ACM, 2014, doi:<a href=\"https://doi.org/10.1145/2597631\">10.1145/2597631</a>.","ieee":"K. Chatterjee and M. Henzinger, “Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition,” <i>Journal of the ACM</i>, vol. 61, no. 3. ACM, 2014."},"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"main_file_link":[{"open_access":"1","url":"https://eprints.cs.univie.ac.at/3933/"}],"quality_controlled":"1","oa_version":"Submitted Version","publist_id":"4883","_id":"2141","related_material":{"record":[{"id":"3165","relation":"earlier_version","status":"public"}]},"day":"01","external_id":{"isi":["000337201400001"]},"author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"}],"date_updated":"2025-09-29T11:45:13Z","title":"Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition","publisher":"ACM","abstract":[{"lang":"eng","text":"The computation of 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(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 Õ(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&gt;n4/3 an earlier bound of O(m ⋅ √m)). We then 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. Our algorithms are the first dynamic algorithms for this problem. We then consider another core graph theoretic problem in verification of probabilistic systems, namely computing the maximal end-component decomposition of a graph. We present two improved static algorithms for the maximal end-component decomposition problem. Our first algorithm is an O(m ⋅ √m)-time algorithm, and our second algorithm is an O(n2)-time algorithm which is obtained using the same technique as for alternating Büchi games. Thus, we obtain an O(min &amp;lcu;m ⋅ √m,n2})-time algorithm improving the long-standing O(n ⋅ m) time bound. Finally, we show how to maintain the maximal end-component decomposition of a graph under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time per edge insertion. Again, our algorithms are the first dynamic algorithms for this problem."}],"date_created":"2018-12-11T11:55:57Z","intvolume":"        61","language":[{"iso":"eng"}],"issue":"3","status":"public","month":"05","publication":"Journal of the ACM","oa":1,"type":"journal_article","ec_funded":1,"isi":1,"article_processing_charge":"No","year":"2014","publication_status":"published","article_number":"a15","date_published":"2014-05-01T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"publisher":"Springer","alternative_title":["LNCS"],"abstract":[{"text":"We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lies in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP ∩ coNP is the long-standing best known bound). We present a variant of the strategy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existential theory of the reals, and establish square-root sum hardness for a related class of games.","lang":"eng"}],"date_created":"2018-12-11T11:56:04Z","intvolume":"      8573","language":[{"iso":"eng"}],"issue":"Part 2","status":"public","month":"01","corr_author":"1","page":"122 - 133","oa":1,"ec_funded":1,"type":"conference","year":"2014","publication_status":"published","date_published":"2014-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":8573,"scopus_import":"1","department":[{"_id":"KrCh"}],"doi":"10.1007/978-3-662-43951-7_11","citation":{"ieee":"K. Chatterjee and R. Ibsen-Jensen, “The complexity of ergodic mean payoff games,” presented at the ICST: International Conference on Software Testing, Verification and Validation, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 122–133.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Mean Payoff Games</i>. Vol. 8573, no. Part 2, Springer, 2014, pp. 122–33, doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">10.1007/978-3-662-43951-7_11</a>.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). The complexity of ergodic mean payoff games (Vol. 8573, pp. 122–133). Presented at the ICST: International Conference on Software Testing, Verification and Validation, Copenhagen, Denmark: Springer. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">https://doi.org/10.1007/978-3-662-43951-7_11</a>","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The complexity of ergodic mean payoff games. ICST: International Conference on Software Testing, Verification and Validation, LNCS, vol. 8573, 122–133.","ama":"Chatterjee K, Ibsen-Jensen R. The complexity of ergodic mean payoff games. In: Vol 8573. Springer; 2014:122-133. doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">10.1007/978-3-662-43951-7_11</a>","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Ergodic Mean Payoff Games,” 8573:122–33. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">https://doi.org/10.1007/978-3-662-43951-7_11</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, in:, Springer, 2014, pp. 122–133."},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1404.5734"}],"oa_version":"Preprint","quality_controlled":"1","publist_id":"4822","_id":"2162","arxiv":1,"related_material":{"record":[{"relation":"earlier_version","id":"5404","status":"public"}]},"day":"01","external_id":{"arxiv":["1404.5734"]},"conference":{"end_date":"2014-07-11","start_date":"2014-07-08","name":"ICST: International Conference on Software Testing, Verification and Validation","location":"Copenhagen, Denmark"},"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"}],"date_updated":"2024-10-21T06:02:53Z","title":"The complexity of ergodic mean payoff games"},{"publisher":"Springer","alternative_title":["LNCS"],"date_created":"2018-12-11T11:56:04Z","abstract":[{"lang":"eng","text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable in general, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games."}],"intvolume":"      8573","language":[{"iso":"eng"}],"issue":"Part 2","month":"01","status":"public","publication":"Lecture Notes in Computer Science","page":"110 - 121","oa":1,"type":"conference","ec_funded":1,"year":"2014","publication_status":"published","date_published":"2014-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":8573,"department":[{"_id":"KrCh"}],"scopus_import":"1","doi":"10.1007/978-3-662-43951-7_10","citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” In <i>Lecture Notes in Computer Science</i>, 8573:110–21. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">https://doi.org/10.1007/978-3-662-43951-7_10</a>.","short":"K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” <i>Lecture Notes in Computer Science</i>, vol. 8573, no. Part 2, Springer, 2014, pp. 110–21, doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">10.1007/978-3-662-43951-7_10</a>.","ieee":"K. Chatterjee and L. Doyen, “Games with a weak adversary,” in <i>Lecture Notes in Computer Science</i>, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 110–121.","ama":"Chatterjee K, Doyen L. Games with a weak adversary. In: <i>Lecture Notes in Computer Science</i>. Vol 8573. Springer; 2014:110-121. doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">10.1007/978-3-662-43951-7_10</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2014). Games with a weak adversary. In <i>Lecture Notes in Computer Science</i> (Vol. 8573, pp. 110–121). Copenhagen, Denmark: Springer. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_10\">https://doi.org/10.1007/978-3-662-43951-7_10</a>","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573, 110–121."},"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"main_file_link":[{"url":"https://arxiv.org/abs/1404.5453","open_access":"1"}],"oa_version":"Preprint","quality_controlled":"1","publist_id":"4821","_id":"2163","arxiv":1,"acknowledgement":"This research was partly supported by European project Cassting (FP7-601148).\r\nTechnical Report under https://research-explorer.app.ist.ac.at/record/5418\r\n","related_material":{"record":[{"id":"5418","relation":"earlier_version","status":"public"}]},"day":"01","external_id":{"arxiv":["1404.5453"]},"conference":{"end_date":"2014-07-11","name":"ICALP: Automata, Languages and Programming","location":"Copenhagen, Denmark","start_date":"2014-07-08"},"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"date_updated":"2024-10-21T06:02:54Z","title":"Games with a weak adversary"},{"date_published":"2014-06-01T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file":[{"file_name":"IST-2012-71-v1+1_Synthesizing_robust_systems.pdf","checksum":"d7f560f3d923f0f00aa10a0652f83273","creator":"system","date_created":"2018-12-12T10:16:44Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":169523,"file_id":"5234","date_updated":"2020-07-14T12:45:31Z"}],"publication_status":"published","year":"2014","article_processing_charge":"No","oa":1,"type":"journal_article","ec_funded":1,"isi":1,"page":"193 - 220","ddc":["621"],"publication":"Acta Informatica","month":"06","status":"public","issue":"3-4","intvolume":"        51","language":[{"iso":"eng"}],"publisher":"Springer","date_created":"2018-12-11T11:56:13Z","has_accepted_license":"1","abstract":[{"text":"Systems should not only be correct but also robust in the sense that they behave reasonably in unexpected situations. This article addresses synthesis of robust reactive systems from temporal specifications. Existing methods allow arbitrary behavior if assumptions in the specification are violated. To overcome this, we define two robustness notions, combine them, and show how to enforce them in synthesis. The first notion applies to safety properties: If safety assumptions are violated temporarily, we require that the system recovers to normal operation with as few errors as possible. The second notion requires that, if liveness assumptions are violated, as many guarantees as possible should be fulfilled nevertheless. We present a synthesis procedure achieving this for the important class of GR(1) specifications, and establish complexity bounds. We also present an implementation of a special case of robustness, and show experimental results.","lang":"eng"}],"title":"Synthesizing robust systems","date_updated":"2025-09-29T11:32:51Z","author":[{"last_name":"Bloem","first_name":"Roderick","full_name":"Bloem, Roderick"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Greimel","first_name":"Karin","full_name":"Greimel, Karin"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A"},{"full_name":"Hofferek, Georg","first_name":"Georg","last_name":"Hofferek"},{"full_name":"Jobstmann, Barbara","last_name":"Jobstmann","first_name":"Barbara"},{"full_name":"Könighofer, Bettina","last_name":"Könighofer","first_name":"Bettina"},{"last_name":"Könighofer","first_name":"Robert","full_name":"Könighofer, Robert"}],"external_id":{"isi":["000335981500004"]},"day":"01","file_date_updated":"2020-07-14T12:45:31Z","article_type":"original","quality_controlled":"1","oa_version":"Submitted Version","_id":"2187","publist_id":"4787","pubrep_id":"71","doi":"10.1007/s00236-013-0191-5","citation":{"short":"R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, G. Hofferek, B. Jobstmann, B. Könighofer, R. Könighofer, Acta Informatica 51 (2014) 193–220.","chicago":"Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger, Georg Hofferek, Barbara Jobstmann, Bettina Könighofer, and Robert Könighofer. “Synthesizing Robust Systems.” <i>Acta Informatica</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00236-013-0191-5\">https://doi.org/10.1007/s00236-013-0191-5</a>.","apa":"Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., Hofferek, G., Jobstmann, B., … Könighofer, R. (2014). Synthesizing robust systems. <i>Acta Informatica</i>. Springer. <a href=\"https://doi.org/10.1007/s00236-013-0191-5\">https://doi.org/10.1007/s00236-013-0191-5</a>","ista":"Bloem R, Chatterjee K, Greimel K, Henzinger TA, Hofferek G, Jobstmann B, Könighofer B, Könighofer R. 2014. Synthesizing robust systems. Acta Informatica. 51(3–4), 193–220.","ama":"Bloem R, Chatterjee K, Greimel K, et al. Synthesizing robust systems. <i>Acta Informatica</i>. 2014;51(3-4):193-220. doi:<a href=\"https://doi.org/10.1007/s00236-013-0191-5\">10.1007/s00236-013-0191-5</a>","ieee":"R. Bloem <i>et al.</i>, “Synthesizing robust systems,” <i>Acta Informatica</i>, vol. 51, no. 3–4. Springer, pp. 193–220, 2014.","mla":"Bloem, Roderick, et al. “Synthesizing Robust Systems.” <i>Acta Informatica</i>, vol. 51, no. 3–4, Springer, 2014, pp. 193–220, doi:<a href=\"https://doi.org/10.1007/s00236-013-0191-5\">10.1007/s00236-013-0191-5</a>."},"project":[{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Reactive Modeling","grant_number":"267989","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"volume":51,"scopus_import":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}]},{"page":"192 - 208","ec_funded":1,"type":"conference","oa":1,"article_processing_charge":"No","year":"2014","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2014-01-01T00:00:00Z","alternative_title":["LNCS"],"date_created":"2018-12-11T11:56:14Z","abstract":[{"text":"We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula φ. The automaton is the product of a master automaton and an array of slave automata, one for each G-subformula of φ. The slave automaton for G ψ is in charge of recognizing whether FG ψ holds. As opposed to standard determinization procedures, the states of all our automata have a clear logical structure, which allows for various optimizations. Our construction subsumes former algorithms for fragments of LTL. Experimental results show improvement in the sizes of the resulting automata compared to existing methods.","lang":"eng"}],"publisher":"Springer","language":[{"iso":"eng"}],"intvolume":"      8559","month":"01","corr_author":"1","status":"public","acknowledgement":"The author is on leave from Faculty of Informatics, Masaryk University, Czech Republic, and partially supported by the Czech Science Foundation, grant No. P202/12/G061.","day":"01","arxiv":1,"conference":{"name":"CAV: Computer Aided Verification"},"external_id":{"arxiv":["1402.3388"]},"author":[{"first_name":"Javier","last_name":"Esparza","full_name":"Esparza, Javier"},{"first_name":"Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2025-06-11T08:01:04Z","title":"From LTL to deterministic automata: A safraless compositional approach","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"scopus_import":"1","volume":8559,"project":[{"grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms"}],"citation":{"short":"J. Esparza, J. Kretinsky, in:, Springer, 2014, pp. 192–208.","chicago":"Esparza, Javier, and Jan Kretinsky. “From LTL to Deterministic Automata: A Safraless Compositional Approach,” 8559:192–208. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">https://doi.org/10.1007/978-3-319-08867-9_13</a>.","ista":"Esparza J, Kretinsky J. 2014. From LTL to deterministic automata: A safraless compositional approach. CAV: Computer Aided Verification, LNCS, vol. 8559, 192–208.","apa":"Esparza, J., &#38; Kretinsky, J. (2014). From LTL to deterministic automata: A safraless compositional approach (Vol. 8559, pp. 192–208). Presented at the CAV: Computer Aided Verification, Springer. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">https://doi.org/10.1007/978-3-319-08867-9_13</a>","ama":"Esparza J, Kretinsky J. From LTL to deterministic automata: A safraless compositional approach. In: Vol 8559. Springer; 2014:192-208. doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">10.1007/978-3-319-08867-9_13</a>","mla":"Esparza, Javier, and Jan Kretinsky. <i>From LTL to Deterministic Automata: A Safraless Compositional Approach</i>. Vol. 8559, Springer, 2014, pp. 192–208, doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_13\">10.1007/978-3-319-08867-9_13</a>.","ieee":"J. Esparza and J. Kretinsky, “From LTL to deterministic automata: A safraless compositional approach,” presented at the CAV: Computer Aided Verification, 2014, vol. 8559, pp. 192–208."},"doi":"10.1007/978-3-319-08867-9_13","publist_id":"4784","_id":"2190","main_file_link":[{"url":"http://arxiv.org/abs/1402.3388","open_access":"1"}],"quality_controlled":"1","oa_version":"Submitted Version"},{"publist_id":"5836","_id":"1375","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1307.4473"}],"oa_version":"Preprint","quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"citation":{"short":"K. Chatterjee, M. Henzinger, S. Krinninger, V. Loitzenbauer, M. Raskin, Theoretical Computer Science 547 (2014) 104–116.","chicago":"Chatterjee, Krishnendu, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, and Michael Raskin. “Approximating the Minimum Cycle Mean.” <i>Theoretical Computer Science</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">https://doi.org/10.1016/j.tcs.2014.06.031</a>.","ista":"Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. 2014. Approximating the minimum cycle mean. Theoretical Computer Science. 547(C), 104–116.","apa":"Chatterjee, K., Henzinger, M., Krinninger, S., Loitzenbauer, V., &#38; Raskin, M. (2014). Approximating the minimum cycle mean. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">https://doi.org/10.1016/j.tcs.2014.06.031</a>","ama":"Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. Approximating the minimum cycle mean. <i>Theoretical Computer Science</i>. 2014;547(C):104-116. doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">10.1016/j.tcs.2014.06.031</a>","mla":"Chatterjee, Krishnendu, et al. “Approximating the Minimum Cycle Mean.” <i>Theoretical Computer Science</i>, vol. 547, no. C, Elsevier, 2014, pp. 104–16, doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">10.1016/j.tcs.2014.06.031</a>.","ieee":"K. Chatterjee, M. Henzinger, S. Krinninger, V. Loitzenbauer, and M. Raskin, “Approximating the minimum cycle mean,” <i>Theoretical Computer Science</i>, vol. 547, no. C. Elsevier, pp. 104–116, 2014."},"doi":"10.1016/j.tcs.2014.06.031","department":[{"_id":"KrCh"}],"scopus_import":"1","volume":547,"date_updated":"2025-09-29T13:17:21Z","title":"Approximating the minimum cycle mean","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"last_name":"Loitzenbauer","first_name":"Veronika","full_name":"Loitzenbauer, Veronika"},{"first_name":"Michael","last_name":"Raskin","full_name":"Raskin, Michael"}],"external_id":{"isi":["000340694000008"],"arxiv":["1307.4473"]},"article_type":"original","day":"28","arxiv":1,"publication":"Theoretical Computer Science","month":"08","status":"public","issue":"C","language":[{"iso":"eng"}],"intvolume":"       547","date_created":"2018-12-11T11:51:40Z","abstract":[{"text":"We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n×n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1+ε)-approximation algorithm for the problem and the running time of our algorithm is Õ(nωlog3(nW/ε)/ε),1 where O(nω) is the time required for the classic n×n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ε)) factor in space a cycle with approximately optimal weight can be computed within the same time bound.","lang":"eng"}],"publisher":"Elsevier","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2014-08-28T00:00:00Z","article_processing_charge":"No","year":"2014","publication_status":"published","type":"journal_article","isi":1,"ec_funded":1,"oa":1,"page":"104 - 116"},{"author":[{"first_name":"Susmit","last_name":"Jha","full_name":"Jha, Susmit"},{"full_name":"Tripakis, Stavros","first_name":"Stavros","last_name":"Tripakis"},{"full_name":"Seshia, Sanjit","last_name":"Seshia","first_name":"Sanjit"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"}],"publication_status":"published","year":"2014","title":"Game theoretic secure localization in wireless sensor networks","date_published":"2014-02-03T00:00:00Z","date_updated":"2024-10-21T06:02:48Z","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","page":"85 - 90","day":"03","conference":{"location":"Cambridge, USA","name":"IOT: Internet of Things","start_date":"2014-10-06","end_date":"2014-10-08"},"type":"conference","oa_version":"None","status":"public","quality_controlled":"1","month":"02","_id":"1853","publist_id":"5247","publisher":"IEEE","abstract":[{"lang":"eng","text":"Wireless sensor networks (WSNs) composed of low-power, low-cost sensor nodes are expected to form the backbone of future intelligent networks for a broad range of civil, industrial and military applications. These sensor nodes are often deployed through random spreading, and function in dynamic environments. Many applications of WSNs such as pollution tracking, forest fire detection, and military surveillance require knowledge of the location of constituent nodes. But the use of technologies such as GPS on all nodes is prohibitive due to power and cost constraints. So, the sensor nodes need to autonomously determine their locations. Most localization techniques use anchor nodes with known locations to determine the position of remaining nodes. Localization techniques have two conflicting requirements. On one hand, an ideal localization technique should be computationally simple and on the other hand, it must be resistant to attacks that compromise anchor nodes. In this paper, we propose a computationally light-weight game theoretic secure localization technique and demonstrate its effectiveness in comparison to existing techniques."}],"department":[{"_id":"KrCh"}],"scopus_import":"1","date_created":"2018-12-11T11:54:22Z","doi":"10.1109/IOT.2014.7030120","citation":{"short":"S. Jha, S. Tripakis, S. Seshia, K. Chatterjee, in:, IEEE, 2014, pp. 85–90.","chicago":"Jha, Susmit, Stavros Tripakis, Sanjit Seshia, and Krishnendu Chatterjee. “Game Theoretic Secure Localization in Wireless Sensor Networks,” 85–90. IEEE, 2014. <a href=\"https://doi.org/10.1109/IOT.2014.7030120\">https://doi.org/10.1109/IOT.2014.7030120</a>.","ista":"Jha S, Tripakis S, Seshia S, Chatterjee K. 2014. Game theoretic secure localization in wireless sensor networks. IOT: Internet of Things, 85–90.","apa":"Jha, S., Tripakis, S., Seshia, S., &#38; Chatterjee, K. (2014). Game theoretic secure localization in wireless sensor networks (pp. 85–90). Presented at the IOT: Internet of Things, Cambridge, USA: IEEE. <a href=\"https://doi.org/10.1109/IOT.2014.7030120\">https://doi.org/10.1109/IOT.2014.7030120</a>","ama":"Jha S, Tripakis S, Seshia S, Chatterjee K. Game theoretic secure localization in wireless sensor networks. In: IEEE; 2014:85-90. doi:<a href=\"https://doi.org/10.1109/IOT.2014.7030120\">10.1109/IOT.2014.7030120</a>","mla":"Jha, Susmit, et al. <i>Game Theoretic Secure Localization in Wireless Sensor Networks</i>. IEEE, 2014, pp. 85–90, doi:<a href=\"https://doi.org/10.1109/IOT.2014.7030120\">10.1109/IOT.2014.7030120</a>.","ieee":"S. Jha, S. Tripakis, S. Seshia, and K. Chatterjee, “Game theoretic secure localization in wireless sensor networks,” presented at the IOT: Internet of Things, Cambridge, USA, 2014, pp. 85–90."},"language":[{"iso":"eng"}]},{"author":[{"first_name":"Dan","last_name":"Landau","full_name":"Landau, Dan"},{"full_name":"Stewart, Chip","last_name":"Stewart","first_name":"Chip"},{"first_name":"Johannes","last_name":"Reiter","orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Lawrence, Michael","last_name":"Lawrence","first_name":"Michael"},{"full_name":"Sougnez, Carrie","last_name":"Sougnez","first_name":"Carrie"},{"full_name":"Brown, Jennifer","first_name":"Jennifer","last_name":"Brown"},{"last_name":"Lopez Guillermo","first_name":"Armando","full_name":"Lopez Guillermo, Armando"},{"last_name":"Gabriel","first_name":"Stacey","full_name":"Gabriel, Stacey"},{"last_name":"Lander","first_name":"Eric","full_name":"Lander, Eric"},{"full_name":"Neuberg, Donna","last_name":"Neuberg","first_name":"Donna"},{"last_name":"López Otín","first_name":"Carlos","full_name":"López Otín, Carlos"},{"last_name":"Campo","first_name":"Elias","full_name":"Campo, Elias"},{"first_name":"Gad","last_name":"Getz","full_name":"Getz, Gad"},{"full_name":"Wu, Catherine","last_name":"Wu","first_name":"Catherine"}],"publication_status":"published","year":"2014","title":"Novel putative driver gene mutations in chronic lymphocytic leukemia (CLL): results from a combined analysis of whole exome sequencing of 262 primary CLL aamples","date_published":"2014-12-04T00:00:00Z","date_updated":"2021-01-12T06:53:50Z","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","page":"1952 - 1952","day":"04","type":"journal_article","issue":"21","publication":"Blood","status":"public","oa_version":"None","month":"12","main_file_link":[{"url":"http://www.bloodjournal.org/content/124/21/1952?sso-checked=true"}],"_id":"1884","publist_id":"5211","publisher":"American Society of Hematology","volume":124,"date_created":"2018-12-11T11:54:32Z","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"Unbiased high-throughput massively parallel sequencing methods have transformed the process of discovery of novel putative driver gene mutations in cancer. In chronic lymphocytic leukemia (CLL), these methods have yielded several unexpected findings, including the driver genes SF3B1, NOTCH1 and POT1. Recent analysis, utilizing down-sampling of existing datasets, has shown that the discovery process of putative drivers is far from complete across cancer. In CLL, while driver gene mutations affecting >10% of patients were efficiently discovered with previously published CLL cohorts of up to 160 samples subjected to whole exome sequencing (WES), this sample size has only 0.78 power to detect drivers affecting 5% of patients, and only 0.12 power for drivers affecting 2% of patients. These calculations emphasize the need to apply unbiased WES to larger patient cohorts."}],"intvolume":"       124","citation":{"apa":"Landau, D., Stewart, C., Reiter, J., Lawrence, M., Sougnez, C., Brown, J., … Wu, C. (2014). Novel putative driver gene mutations in chronic lymphocytic leukemia (CLL): results from a combined analysis of whole exome sequencing of 262 primary CLL aamples. <i>Blood</i>. American Society of Hematology.","ista":"Landau D, Stewart C, Reiter J, Lawrence M, Sougnez C, Brown J, Lopez Guillermo A, Gabriel S, Lander E, Neuberg D, López Otín C, Campo E, Getz G, Wu C. 2014. Novel putative driver gene mutations in chronic lymphocytic leukemia (CLL): results from a combined analysis of whole exome sequencing of 262 primary CLL aamples. Blood. 124(21), 1952–1952.","ama":"Landau D, Stewart C, Reiter J, et al. Novel putative driver gene mutations in chronic lymphocytic leukemia (CLL): results from a combined analysis of whole exome sequencing of 262 primary CLL aamples. <i>Blood</i>. 2014;124(21):1952-1952.","ieee":"D. Landau <i>et al.</i>, “Novel putative driver gene mutations in chronic lymphocytic leukemia (CLL): results from a combined analysis of whole exome sequencing of 262 primary CLL aamples,” <i>Blood</i>, vol. 124, no. 21. American Society of Hematology, pp. 1952–1952, 2014.","mla":"Landau, Dan, et al. “Novel Putative Driver Gene Mutations in Chronic Lymphocytic Leukemia (CLL): Results from a Combined Analysis of Whole Exome Sequencing of 262 Primary CLL Aamples.” <i>Blood</i>, vol. 124, no. 21, American Society of Hematology, 2014, pp. 1952–1952.","short":"D. Landau, C. Stewart, J. Reiter, M. Lawrence, C. Sougnez, J. Brown, A. Lopez Guillermo, S. Gabriel, E. Lander, D. Neuberg, C. López Otín, E. Campo, G. Getz, C. Wu, Blood 124 (2014) 1952–1952.","chicago":"Landau, Dan, Chip Stewart, Johannes Reiter, Michael Lawrence, Carrie Sougnez, Jennifer Brown, Armando Lopez Guillermo, et al. “Novel Putative Driver Gene Mutations in Chronic Lymphocytic Leukemia (CLL): Results from a Combined Analysis of Whole Exome Sequencing of 262 Primary CLL Aamples.” <i>Blood</i>. American Society of Hematology, 2014."},"language":[{"iso":"eng"}]},{"pubrep_id":"952","_id":"475","publist_id":"7345","quality_controlled":"1","oa_version":"Published Version","scopus_import":"1","department":[{"_id":"KrCh"}],"volume":146,"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","call_identifier":"FWF","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"mla":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, vol. 146, Open Publishing Association, 2014, pp. 83–90, doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>.","ieee":"B. Aminof and S. Rubin, “First cycle games,” in <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, Grenoble, France, 2014, vol. 146, pp. 83–90.","ista":"Aminof B, Rubin S. 2014. First cycle games. Electronic Proceedings in Theoretical Computer Science, EPTCS. SR: Strategic Reasoning, EPTCS, vol. 146, 83–90.","ama":"Aminof B, Rubin S. First cycle games. In: <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>. Vol 146. Open Publishing Association; 2014:83-90. doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>","apa":"Aminof, B., &#38; Rubin, S. (2014). First cycle games. In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i> (Vol. 146, pp. 83–90). Grenoble, France: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>","chicago":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, 146:83–90. Open Publishing Association, 2014. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>.","short":"B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association, 2014, pp. 83–90."},"doi":"10.4204/EPTCS.146.11","author":[{"id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","full_name":"Aminof, Benjamin","first_name":"Benjamin","last_name":"Aminof"},{"full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","first_name":"Sasha","last_name":"Rubin"}],"title":"First cycle games","date_updated":"2025-04-14T13:51:05Z","day":"01","file_date_updated":"2020-07-14T12:46:35Z","arxiv":1,"conference":{"location":"Grenoble, France","name":"SR: Strategic Reasoning","start_date":"2014-04-05","end_date":"2014-04-06"},"external_id":{"arxiv":["1404.0843"]},"ddc":["004"],"publication":"Electronic Proceedings in Theoretical Computer Science, EPTCS","corr_author":"1","month":"04","status":"public","date_created":"2018-12-11T11:46:41Z","abstract":[{"lang":"eng","text":"First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in Memoryless determinacy of parity and mean payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that θ (n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard. "}],"has_accepted_license":"1","alternative_title":["EPTCS"],"publisher":"Open Publishing Association","language":[{"iso":"eng"}],"intvolume":"       146","publication_status":"published","article_processing_charge":"No","year":"2014","file":[{"relation":"main_file","date_created":"2018-12-12T10:17:08Z","file_name":"IST-2018-952-v1+1_2014_Rubin_First_cycle.pdf","creator":"system","checksum":"4d7b4ab82980cca2b96ac7703992a8c8","file_size":100115,"content_type":"application/pdf","access_level":"open_access","file_id":"5260","date_updated":"2020-07-14T12:46:35Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2014-04-01T00:00:00Z","page":"83 - 90","ec_funded":1,"type":"conference","oa":1},{"pubrep_id":"153","_id":"5412","month":"01","status":"public","oa_version":"Published Version","ddc":["000"],"alternative_title":["IST Austria Technical Report"],"department":[{"_id":"KrCh"}],"has_accepted_license":"1","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"date_created":"2018-12-12T11:39:11Z","publisher":"IST Austria","language":[{"iso":"eng"}],"citation":{"short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 31p.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014."},"doi":"10.15479/AT:IST-2014-153-v1-1","year":"2014","publication_status":"published","file":[{"file_size":423322,"access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T11:53:39Z","relation":"main_file","checksum":"4d6cda4bebed970926403ad6ad8c745f","file_name":"IST-2014-153-v1+1_main.pdf","creator":"system","date_updated":"2020-07-14T12:46:47Z","file_id":"5500"}],"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","first_name":"Przemyslaw","last_name":"Daca"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-04-15T07:56:48Z","date_published":"2014-01-29T00:00:00Z","title":"CEGAR for qualitative analysis of probabilistic systems","related_material":{"record":[{"id":"5413","relation":"later_version","status":"public"},{"status":"public","id":"5414","relation":"later_version"},{"id":"2063","relation":"later_version","status":"public"}]},"file_date_updated":"2020-07-14T12:46:47Z","publication_identifier":{"issn":["2664-1690"]},"day":"29","page":"31","type":"technical_report","oa":1},{"type":"technical_report","oa":1,"day":"06","file_date_updated":"2020-07-14T12:46:47Z","related_material":{"record":[{"relation":"earlier_version","id":"5412","status":"public"},{"id":"5414","relation":"later_version","status":"public"},{"status":"public","relation":"later_version","id":"2063"}]},"publication_identifier":{"issn":["2664-1690"]},"page":"33","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"CEGAR for qualitative analysis of probabilistic systems","date_published":"2014-02-06T00:00:00Z","date_updated":"2025-04-15T07:56:48Z","publication_status":"published","year":"2014","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","first_name":"Przemyslaw","last_name":"Daca"},{"first_name":"Martin","last_name":"Chmelik","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"file":[{"checksum":"ce4967a184d84863eec76c66cbac1614","creator":"system","file_name":"IST-2014-153-v2+2_main.pdf","relation":"main_file","date_created":"2018-12-12T11:54:17Z","content_type":"application/pdf","access_level":"open_access","file_size":606049,"file_id":"5539","date_updated":"2020-07-14T12:46:47Z"}],"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-153-v2-2","citation":{"ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>."},"department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:11Z","has_accepted_license":"1","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","_id":"5413","month":"02","ddc":["000"],"status":"public","oa_version":"Published Version","pubrep_id":"164"},{"oa_version":"Published Version","status":"public","ddc":["000"],"month":"02","_id":"5414","pubrep_id":"165","doi":"10.15479/AT:IST-2014-153-v3-1","citation":{"short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014."},"language":[{"iso":"eng"}],"publisher":"IST Austria","date_created":"2018-12-12T11:39:12Z","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"has_accepted_license":"1","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"title":"CEGAR for qualitative analysis of probabilistic systems","date_published":"2014-02-07T00:00:00Z","date_updated":"2025-04-15T07:56:48Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Przemyslaw","last_name":"Daca","id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik"}],"file":[{"date_updated":"2020-07-14T12:46:48Z","file_id":"5464","file_size":606227,"access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T11:53:03Z","relation":"main_file","creator":"system","file_name":"IST-2014-153-v3+1_main.pdf","checksum":"87b93fe9af71fc5c94b0eb6151537e11"}],"publication_status":"published","year":"2014","oa":1,"type":"technical_report","page":"33","day":"07","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5412"},{"status":"public","relation":"earlier_version","id":"5413"},{"status":"public","relation":"later_version","id":"2063"}]},"file_date_updated":"2020-07-14T12:46:48Z","publication_identifier":{"issn":["2664-1690"]}},{"_id":"5418","month":"03","status":"public","ddc":["000","005"],"oa_version":"Published Version","pubrep_id":"176","language":[{"iso":"eng"}],"citation":{"ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>.","apa":"Chatterjee, K., &#38; Doyen, L. (2014). <i>Games with a weak adversary</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.","ama":"Chatterjee K, Doyen L. <i>Games with a Weak Adversary</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>.","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014."},"doi":"10.15479/AT:IST-2014-176-v1-1","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","abstract":[{"lang":"eng","text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results."}],"date_created":"2018-12-12T11:39:13Z","department":[{"_id":"KrCh"}],"publisher":"IST Austria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2014-03-22T00:00:00Z","date_updated":"2025-04-15T07:55:59Z","title":"Games with a weak adversary","year":"2014","publication_status":"published","file":[{"file_size":328253,"access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T11:53:07Z","relation":"main_file","file_name":"IST-2014-176-v1+1_icalp_14.pdf","creator":"system","checksum":"1d6958aa60050e1c3e932c6e5f34c39f","date_updated":"2020-07-14T12:46:49Z","file_id":"5468"}],"author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}],"type":"technical_report","oa":1,"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:49Z","related_material":{"record":[{"id":"2163","relation":"later_version","status":"public"}]},"day":"22","page":"18"},{"citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>."},"doi":"10.15479/AT:IST-2014-187-v1-1","language":[{"iso":"eng"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","abstract":[{"lang":"eng","text":"We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:\r\n1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).\r\n2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.\r\nOur algorithms improve all existing results, and use very simple data structures."}],"date_created":"2018-12-12T11:39:13Z","department":[{"_id":"KrCh"}],"oa_version":"Published Version","status":"public","month":"04","ddc":["000"],"_id":"5419","pubrep_id":"187","oa":1,"type":"technical_report","page":"34","publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:50Z","day":"14","date_updated":"2021-01-12T08:02:03Z","date_published":"2014-04-14T00:00:00Z","title":"Improved algorithms for reachability and shortest path on low tree-width graphs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_id":"5548","date_updated":"2020-07-14T12:46:50Z","date_created":"2018-12-12T11:54:25Z","relation":"main_file","file_name":"IST-2014-187-v1+1_main_full_tech.pdf","creator":"system","checksum":"c608e66030a4bf51d2d99b451f539b99","file_size":670031,"access_level":"open_access","content_type":"application/pdf"}],"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722"}],"year":"2014","publication_status":"published"},{"file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"day":"14","page":"49","type":"technical_report","oa":1,"year":"2014","publication_status":"published","file":[{"file_id":"5520","date_updated":"2020-07-14T12:46:50Z","checksum":"49e0fd3e62650346daf7dc04604f7a0a","file_name":"IST-2014-191-v1+1_main_full.pdf","creator":"system","date_created":"2018-12-12T11:53:58Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":584368}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:02:05Z","date_published":"2014-04-14T00:00:00Z","title":"The value 1 problem for concurrent mean-payoff games","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","abstract":[{"lang":"eng","text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy)."}],"date_created":"2018-12-12T11:39:14Z","department":[{"_id":"KrCh"}],"publisher":"IST Austria","language":[{"iso":"eng"}],"citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>"},"doi":"10.15479/AT:IST-2014-191-v1-1","pubrep_id":"191","_id":"5420","month":"04","status":"public","ddc":["000","005"],"oa_version":"Published Version"},{"alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time."}],"department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:14Z","has_accepted_license":"1","publisher":"IST Austria","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-190-v2-2","citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolution on Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2014). <i>The complexity of evolution on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolution on graphs</i>. IST Austria, 2014.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on Graphs, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>."},"pubrep_id":"190","_id":"5421","ddc":["000","005"],"month":"04","oa_version":"Published Version","status":"public","publication_identifier":{"issn":["2664-1690"]},"related_material":{"record":[{"status":"public","relation":"later_version","id":"5432"},{"relation":"later_version","id":"5440","status":"public"}]},"file_date_updated":"2020-07-14T12:46:50Z","day":"18","page":"27","type":"technical_report","oa":1,"year":"2014","publication_status":"published","file":[{"date_updated":"2020-07-14T12:46:50Z","file_id":"5538","file_size":443529,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:54:16Z","creator":"system","file_name":"IST-2014-190-v2+2_main_full.pdf","checksum":"42f3d8b563286eb0d903832bd9a848d3"},{"date_updated":"2020-07-14T12:46:50Z","file_id":"6852","access_level":"open_access","content_type":"application/pdf","file_size":440911,"checksum":"0c9a2fd822309719634495a35957e34d","file_name":"IST-2014-190-v1+1_main_full.pdf","creator":"kschuh","date_created":"2019-09-06T07:30:20Z","relation":"main_file"}],"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T12:26:33Z","date_published":"2014-04-18T00:00:00Z","title":"The complexity of evolution on graphs"}]