[{"issue":"3","external_id":{"arxiv":["1104.3348"]},"status":"public","oa":1,"citation":{"ista":"Chatterjee K, Henzinger MH, Joglekar M, Shah N. 2013. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. Formal Methods in System Design. 42(3), 301–327.","short":"K. Chatterjee, M.H. Henzinger, M. Joglekar, N. Shah, Formal Methods in System Design 42 (2013) 301–327.","mla":"Chatterjee, Krishnendu, et al. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” <i>Formal Methods in System Design</i>, vol. 42, no. 3, Springer, 2013, pp. 301–27, doi:<a href=\"https://doi.org/10.1007/s10703-012-0180-2\">10.1007/s10703-012-0180-2</a>.","ama":"Chatterjee K, Henzinger MH, Joglekar M, Shah N. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. <i>Formal Methods in System Design</i>. 2013;42(3):301-327. doi:<a href=\"https://doi.org/10.1007/s10703-012-0180-2\">10.1007/s10703-012-0180-2</a>","apa":"Chatterjee, K., Henzinger, M. H., Joglekar, M., &#38; Shah, N. (2013). Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-012-0180-2\">https://doi.org/10.1007/s10703-012-0180-2</a>","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Nisarg Shah. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” <i>Formal Methods in System Design</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s10703-012-0180-2\">https://doi.org/10.1007/s10703-012-0180-2</a>.","ieee":"K. Chatterjee, M. H. Henzinger, M. Joglekar, and N. Shah, “Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives,” <i>Formal Methods in System Design</i>, vol. 42, no. 3. Springer, pp. 301–327, 2013."},"user_id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd","type":"journal_article","volume":42,"page":"301 - 327","year":"2013","_id":"2831","arxiv":1,"abstract":[{"text":"We consider Markov decision processes (MDPs) with Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes O(n · √ m) symbolic steps as compared to the previous known algorithm that takes O(n 2) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes O(n · √ n) symbolic steps, as compared to the previous known O(n 2) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires O(n · √ K) symbolic steps, where K is the maximal number of edges of strongly connected components (scc's) of the MDP. The win-lose algorithm requires symbolic computation of scc's. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5×n symbolic steps, whereas our new algorithm takes 4×n symbolic steps.","lang":"eng"}],"publisher":"Springer","publication":"Formal Methods in System Design","title":"Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives","department":[{"_id":"KrCh"}],"publist_id":"3968","ec_funded":1,"date_created":"2018-12-11T11:59:49Z","oa_version":"Preprint","day":"01","month":"06","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        42","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1104.3348"}],"article_processing_charge":"No","date_updated":"2023-02-23T11:23:04Z","related_material":{"record":[{"id":"3342","relation":"earlier_version","status":"public"}]},"doi":"10.1007/s10703-012-0180-2","date_published":"2013-06-01T00:00:00Z","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Joglekar, Manas","first_name":"Manas","last_name":"Joglekar"},{"full_name":"Shah, Nisarg","last_name":"Shah","first_name":"Nisarg"}],"quality_controlled":"1","scopus_import":"1"},{"page":"825 - 859","volume":26,"type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2836","year":"2013","oa":1,"status":"public","external_id":{"arxiv":["1004.2697"]},"issue":"4","citation":{"ama":"Chatterjee K, Raman V. Assume-guarantee synthesis for digital contract signing. <i>Formal Aspects of Computing</i>. 2013;26(4):825-859. doi:<a href=\"https://doi.org/10.1007/s00165-013-0283-6\">10.1007/s00165-013-0283-6</a>","ista":"Chatterjee K, Raman V. 2013. Assume-guarantee synthesis for digital contract signing. Formal Aspects of Computing. 26(4), 825–859.","mla":"Chatterjee, Krishnendu, and Vishwanath Raman. “Assume-Guarantee Synthesis for Digital Contract Signing.” <i>Formal Aspects of Computing</i>, vol. 26, no. 4, Springer, 2013, pp. 825–59, doi:<a href=\"https://doi.org/10.1007/s00165-013-0283-6\">10.1007/s00165-013-0283-6</a>.","short":"K. Chatterjee, V. Raman, Formal Aspects of Computing 26 (2013) 825–859.","chicago":"Chatterjee, Krishnendu, and Vishwanath Raman. “Assume-Guarantee Synthesis for Digital Contract Signing.” <i>Formal Aspects of Computing</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s00165-013-0283-6\">https://doi.org/10.1007/s00165-013-0283-6</a>.","ieee":"K. Chatterjee and V. Raman, “Assume-guarantee synthesis for digital contract signing,” <i>Formal Aspects of Computing</i>, vol. 26, no. 4. Springer, pp. 825–859, 2013.","apa":"Chatterjee, K., &#38; Raman, V. (2013). Assume-guarantee synthesis for digital contract signing. <i>Formal Aspects of Computing</i>. Springer. <a href=\"https://doi.org/10.1007/s00165-013-0283-6\">https://doi.org/10.1007/s00165-013-0283-6</a>"},"department":[{"_id":"KrCh"}],"title":"Assume-guarantee synthesis for digital contract signing","publication":"Formal Aspects of Computing","publisher":"Springer","oa_version":"Preprint","date_created":"2018-12-11T11:59:51Z","ec_funded":1,"publist_id":"3963","arxiv":1,"abstract":[{"lang":"eng","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 and the trusted third party as path formulas in linear temporal logic and prove that the satisfaction of these objectives imply fairness; a property required of fair exchange protocols. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of AGS as follows: (a) any solution of AGS is attack-free; no subset of participants can violate the objectives of the other participants; (b) the Asokan-Shoup-Waidner certified mail protocol that has known vulnerabilities is not a solution of AGS; (c) the Kremer-Markowitch non-repudiation protocol is a solution of AGS; and (d) AGS presents a new and symmetric fair non-repudiation protocol that is attack-free. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can both automatically discover vulnerabilities in protocols and generate correct protocols. The solution to AGS can be computed efficiently as the secure equilibrium solution of three-player graph games. "}],"main_file_link":[{"url":"http://arxiv.org/abs/1004.2697","open_access":"1"}],"intvolume":"        26","publication_status":"published","day":"04","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"month":"07","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Raman","first_name":"Vishwanath","full_name":"Raman, Vishwanath"}],"date_published":"2013-07-04T00:00:00Z","doi":"10.1007/s00165-013-0283-6","date_updated":"2021-01-12T07:00:06Z","scopus_import":1,"quality_controlled":"1"},{"abstract":[{"lang":"eng","text":"We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. First, we present a simple proof of the fact that in concurrent reachability games, for all ε&gt;0, memoryless ε-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an ε-optimal strategy achieves the objective with probability within ε of the value of the game. In contrast to previous proofs of this fact, our proof is more elementary and more combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives. Finally, we present a strategy-improvement algorithm for turn-based stochastic games (where each player selects moves in turns) with safety objectives. Our algorithms yield sequences of player-1 strategies which ensure probabilities of winning that converge monotonically (from below) to the value of the game. © 2012 Elsevier Inc."}],"title":"Strategy improvement for concurrent reachability and turn based stochastic safety games","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication":"Journal of Computer and System Sciences","publisher":"Elsevier","oa_version":"Published Version","ec_funded":1,"date_created":"2018-12-11T11:59:57Z","publist_id":"3938","status":"public","oa":1,"acknowledgement":"This work was partially supported in part by the NSF grants CCR-0132780, CNS-0720884, CCR-0225610, by the Swiss National Science Foundation, ERC Start Grant Graph Games (Project No. 279307), FWF NFN Grant S11407-N23 (RiSE), and a Microsoft faculty fellows","article_type":"original","issue":"5","citation":{"ama":"Chatterjee K, De Alfaro L, Henzinger TA. Strategy improvement for concurrent reachability and turn based stochastic safety games. <i>Journal of Computer and System Sciences</i>. 2013;79(5):640-657. doi:<a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">10.1016/j.jcss.2012.12.001</a>","mla":"Chatterjee, Krishnendu, et al. “Strategy Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.” <i>Journal of Computer and System Sciences</i>, vol. 79, no. 5, Elsevier, 2013, pp. 640–57, doi:<a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">10.1016/j.jcss.2012.12.001</a>.","short":"K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System Sciences 79 (2013) 640–657.","ista":"Chatterjee K, De Alfaro L, Henzinger TA. 2013. Strategy improvement for concurrent reachability and turn based stochastic safety games. Journal of Computer and System Sciences. 79(5), 640–657.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Strategy Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2013. <a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">https://doi.org/10.1016/j.jcss.2012.12.001</a>.","ieee":"K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Strategy improvement for concurrent reachability and turn based stochastic safety games,” <i>Journal of Computer and System Sciences</i>, vol. 79, no. 5. Elsevier, pp. 640–657, 2013.","apa":"Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2013). Strategy improvement for concurrent reachability and turn based stochastic safety games. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">https://doi.org/10.1016/j.jcss.2012.12.001</a>"},"page":"640 - 657","volume":79,"type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2854","year":"2013","has_accepted_license":"1","pubrep_id":"388","date_published":"2013-08-01T00:00:00Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Luca","last_name":"De Alfaro","full_name":"De Alfaro, Luca"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"}],"date_updated":"2021-01-12T07:00:16Z","doi":"10.1016/j.jcss.2012.12.001","article_processing_charge":"No","scopus_import":1,"quality_controlled":"1","file_date_updated":"2020-07-14T12:45:51Z","tmp":{"short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)"},"day":"01","ddc":["000"],"language":[{"iso":"eng"}],"project":[{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"month":"08","intvolume":"        79","publication_status":"published","file":[{"relation":"main_file","access_level":"open_access","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T10:18:48Z","date_updated":"2020-07-14T12:45:51Z","file_id":"5370","file_size":425488,"file_name":"IST-2015-388-v1+1_1-s2.0-S0022000012001778-main.pdf","checksum":"6d3ee12cceb946a0abe69594b6a22409"}]},{"file_date_updated":"2020-07-14T12:45:51Z","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"},"date_published":"2013-01-01T00:00:00Z","pubrep_id":"415","author":[{"last_name":"Reiter","orcid":"0000-0002-0170-7353","first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","full_name":"Reiter, Johannes"},{"first_name":"Ivana","last_name":"Božić","full_name":"Božić, Ivana"},{"full_name":"Allen, Benjamin","id":"135B5B70-E9D2-11E9-BD74-BB415DA2B523","first_name":"Benjamin","last_name":"Allen"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"1400"}]},"date_updated":"2023-09-07T11:40:43Z","doi":"10.1111/eva.12020","scopus_import":1,"quality_controlled":"1","intvolume":"         6","file":[{"relation":"main_file","access_level":"open_access","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T10:15:50Z","date_updated":"2020-07-14T12:45:51Z","file_id":"5173","file_size":1172037,"checksum":"e2955b3889f8a823c3d5a72cb16f8957","file_name":"IST-2016-415-v1+1_Reiter_et_al-2013-Evolutionary_Applications.pdf"}],"publication_status":"published","ddc":["570"],"day":"01","month":"01","language":[{"iso":"eng"}],"project":[{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407","call_identifier":"FWF"}],"publication":"Evolutionary Applications","department":[{"_id":"KrCh"}],"title":"The effect of one additional driver mutation on tumor progression","publisher":"Wiley-Blackwell","date_created":"2018-12-11T11:59:58Z","ec_funded":1,"oa_version":"Published Version","publist_id":"3931","abstract":[{"text":"Tumor growth is caused by the acquisition of driver mutations, which enhance the net reproductive rate of cells. Driver mutations may increase cell division, reduce cell death, or allow cells to overcome density-limiting effects. We study the dynamics of tumor growth as one additional driver mutation is acquired. Our models are based on two-type branching processes that terminate in either tumor disappearance or tumor detection. In our first model, both cell types grow exponentially, with a faster rate for cells carrying the additional driver. We find that the additional driver mutation does not affect the survival probability of the lesion, but can substantially reduce the time to reach the detectable size if the lesion is slow growing. In our second model, cells lacking the additional driver cannot exceed a fixed carrying capacity, due to density limitations. In this case, the time to detection depends strongly on this carrying capacity. Our model provides a quantitative framework for studying tumor dynamics during different stages of progression. We observe that early, small lesions need additional drivers, while late stage metastases are only marginally affected by them. These results help to explain why additional driver mutations are typically not detected in fast-growing metastases.","lang":"eng"}],"volume":6,"page":"34 - 45","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","_id":"2858","year":"2013","has_accepted_license":"1","oa":1,"status":"public","issue":"1","citation":{"ista":"Reiter J, Božić I, Allen B, Chatterjee K, Nowak M. 2013. The effect of one additional driver mutation on tumor progression. Evolutionary Applications. 6(1), 34–45.","short":"J. Reiter, I. Božić, B. Allen, K. Chatterjee, M. Nowak, Evolutionary Applications 6 (2013) 34–45.","mla":"Reiter, Johannes, et al. “The Effect of One Additional Driver Mutation on Tumor Progression.” <i>Evolutionary Applications</i>, vol. 6, no. 1, Wiley-Blackwell, 2013, pp. 34–45, doi:<a href=\"https://doi.org/10.1111/eva.12020\">10.1111/eva.12020</a>.","ama":"Reiter J, Božić I, Allen B, Chatterjee K, Nowak M. The effect of one additional driver mutation on tumor progression. <i>Evolutionary Applications</i>. 2013;6(1):34-45. doi:<a href=\"https://doi.org/10.1111/eva.12020\">10.1111/eva.12020</a>","apa":"Reiter, J., Božić, I., Allen, B., Chatterjee, K., &#38; Nowak, M. (2013). The effect of one additional driver mutation on tumor progression. <i>Evolutionary Applications</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/eva.12020\">https://doi.org/10.1111/eva.12020</a>","chicago":"Reiter, Johannes, Ivana Božić, Benjamin Allen, Krishnendu Chatterjee, and Martin Nowak. “The Effect of One Additional Driver Mutation on Tumor Progression.” <i>Evolutionary Applications</i>. Wiley-Blackwell, 2013. <a href=\"https://doi.org/10.1111/eva.12020\">https://doi.org/10.1111/eva.12020</a>.","ieee":"J. Reiter, I. Božić, B. Allen, K. Chatterjee, and M. Nowak, “The effect of one additional driver mutation on tumor progression,” <i>Evolutionary Applications</i>, vol. 6, no. 1. Wiley-Blackwell, pp. 34–45, 2013."}},{"series_title":"Lecture Notes in Computer Science","abstract":[{"lang":"eng","text":"We focus on the realizability problem of Message Sequence Graphs (MSG), i.e. the problem whether a given MSG specification is correctly distributable among parallel components communicating via messages. This fundamental problem of MSG is known to be undecidable. We introduce a well motivated restricted class of MSG, so called controllable-choice MSG, and show that all its models are realizable and moreover it is decidable whether a given MSG model is a member of this class. In more detail, this class of MSG specifications admits a deadlock-free realization by overloading existing messages with additional bounded control data. We also show that the presented class is the largest known subclass of MSG that allows for deadlock-free realization."}],"publist_id":"3873","date_created":"2018-12-11T12:00:09Z","ec_funded":1,"oa_version":"Submitted Version","publisher":"Springer","department":[{"_id":"KrCh"}],"title":"Controllable-choice message sequence graphs","citation":{"ista":"Chmelik M, Řehák V. 2013. Controllable-choice message sequence graphs. 7721, 118–130.","mla":"Chmelik, Martin, and Vojtěch Řehák. <i>Controllable-Choice Message Sequence Graphs</i>. Vol. 7721, Springer, 2013, pp. 118–30, doi:<a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">10.1007/978-3-642-36046-6_12</a>.","short":"M. Chmelik, V. Řehák, 7721 (2013) 118–130.","ama":"Chmelik M, Řehák V. Controllable-choice message sequence graphs. 2013;7721:118-130. doi:<a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">10.1007/978-3-642-36046-6_12</a>","apa":"Chmelik, M., &#38; Řehák, V. (2013). Controllable-choice message sequence graphs. Presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Znojmo, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">https://doi.org/10.1007/978-3-642-36046-6_12</a>","chicago":"Chmelik, Martin, and Vojtěch Řehák. “Controllable-Choice Message Sequence Graphs.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">https://doi.org/10.1007/978-3-642-36046-6_12</a>.","ieee":"M. Chmelik and V. Řehák, “Controllable-choice message sequence graphs,” vol. 7721. Springer, pp. 118–130, 2013."},"status":"public","oa":1,"year":"2013","_id":"2886","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","volume":7721,"page":"118 - 130","quality_controlled":"1","scopus_import":1,"alternative_title":["LNCS"],"date_updated":"2020-08-11T10:09:52Z","doi":"10.1007/978-3-642-36046-6_12","date_published":"2013-01-09T00:00:00Z","author":[{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"},{"full_name":"Řehák, Vojtěch","last_name":"Řehák","first_name":"Vojtěch"}],"conference":{"start_date":"2012-10-25","location":"Znojmo, Czech Republic","end_date":"2012-10-28","name":"MEMICS: Mathematical and Engineering Methods in Computer Science"},"month":"01","language":[{"iso":"eng"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"day":"09","publication_status":"published","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1209.4499"}],"intvolume":"      7721"},{"volume":42,"page":"142 - 174","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","intvolume":"        42","_id":"3116","year":"2013","publication_status":"published","status":"public","acknowledgement":"This research was supported in part by the National Science Foundation CAREER award CCR-0132780, by the ONR grant N00014-02-1-0671, by the National Science Foundation grants CCR-0427202 and CCR-0234690, and by the ARP award TO.030.MM.D.","issue":"2","day":"01","citation":{"ieee":"K. Chatterjee, L. De Alfaro, M. Faella, R. Majumdar, and V. Raman, “Code aware resource management,” <i>Formal Methods in System Design</i>, vol. 42, no. 2. Springer, pp. 142–174, 2013.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, Marco Faella, Ritankar Majumdar, and Vishwanath Raman. “Code Aware Resource Management.” <i>Formal Methods in System Design</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s10703-012-0170-4\">https://doi.org/10.1007/s10703-012-0170-4</a>.","apa":"Chatterjee, K., De Alfaro, L., Faella, M., Majumdar, R., &#38; Raman, V. (2013). Code aware resource management. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-012-0170-4\">https://doi.org/10.1007/s10703-012-0170-4</a>","ama":"Chatterjee K, De Alfaro L, Faella M, Majumdar R, Raman V. Code aware resource management. <i>Formal Methods in System Design</i>. 2013;42(2):142-174. doi:<a href=\"https://doi.org/10.1007/s10703-012-0170-4\">10.1007/s10703-012-0170-4</a>","ista":"Chatterjee K, De Alfaro L, Faella M, Majumdar R, Raman V. 2013. Code aware resource management. Formal Methods in System Design. 42(2), 142–174.","short":"K. Chatterjee, L. De Alfaro, M. Faella, R. Majumdar, V. Raman, Formal Methods in System Design 42 (2013) 142–174.","mla":"Chatterjee, Krishnendu, et al. “Code Aware Resource Management.” <i>Formal Methods in System Design</i>, vol. 42, no. 2, Springer, 2013, pp. 142–74, doi:<a href=\"https://doi.org/10.1007/s10703-012-0170-4\">10.1007/s10703-012-0170-4</a>."},"month":"04","language":[{"iso":"eng"}],"publication":"Formal Methods in System Design","department":[{"_id":"KrCh"}],"title":"Code aware resource management","publisher":"Springer","date_created":"2018-12-11T12:01:29Z","oa_version":"None","publist_id":"3583","date_published":"2013-04-01T00:00:00Z","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Luca","last_name":"De Alfaro","full_name":"De Alfaro, Luca"},{"last_name":"Faella","first_name":"Marco","full_name":"Faella, Marco"},{"full_name":"Majumdar, Ritankar","first_name":"Ritankar","last_name":"Majumdar"},{"full_name":"Raman, Vishwanath","first_name":"Vishwanath","last_name":"Raman"}],"doi":"10.1007/s10703-012-0170-4","date_updated":"2021-01-12T07:41:10Z","scopus_import":1,"abstract":[{"text":"Multithreaded programs coordinate their interaction through synchronization primitives like mutexes and semaphores, which are managed by an OS-provided resource manager. We propose algorithms for the automatic construction of code-aware resource managers for multithreaded embedded applications. Such managers use knowledge about the structure and resource usage (mutex and semaphore usage) of the threads to guarantee deadlock freedom and progress while managing resources in an efficient way. Our algorithms compute managers as winning strategies in certain infinite games, and produce a compact code description of these strategies. We have implemented the algorithms in the tool Cynthesis. Given a multithreaded program in C, the tool produces C code implementing a code-aware resource manager. We show in experiments that Cynthesis produces compact resource managers within a few minutes on a set of embedded benchmarks with up to 6 threads. © 2012 Springer Science+Business Media, LLC.","lang":"eng"}],"quality_controlled":"1"},{"conference":{"name":"LATA: Conference on Language and Automata Theory and Applications","end_date":"2013-04-05","location":"Bilbao, Spain","start_date":"2013-04-02"},"quality_controlled":"1","scopus_import":"1","article_processing_charge":"No","doi":"10.1007/978-3-642-37064-9_20","date_updated":"2023-09-05T15:10:38Z","alternative_title":["LNCS"],"date_published":"2013-04-15T00:00:00Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Siddhesh","last_name":"Chaubal","full_name":"Chaubal, Siddhesh"},{"last_name":"Rubin","first_name":"Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","full_name":"Rubin, Sasha"}],"publication_status":"published","intvolume":"      7810","month":"04","language":[{"iso":"eng"}],"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"day":"15","ec_funded":1,"date_created":"2022-03-21T07:56:21Z","oa_version":"None","publisher":"Springer Nature","publication":"7th International Conference on Language and Automata Theory and Applications","title":"How to travel between languages","department":[{"_id":"KrCh"}],"series_title":"LNCS","abstract":[{"text":"We consider how to edit strings from a source language so that the edited strings belong to a target language, where the languages are given as deterministic finite automata. Non-streaming (or offline) transducers perform edits given the whole source string. We show that the class of deterministic one-pass transducers with registers along with increment and min operation suffices for computing optimal edit distance, whereas the same class of transducers without the min operation is not sufficient. Streaming (or online) transducers perform edits as the letters of the source string are received. We present a polynomial time algorithm for the partial-repair problem that given a bound α asks for the construction of a deterministic streaming transducer (if one exists) that ensures that the ‘maximum fraction’ η of the strings of the source language are edited, within cost α, to the target language.","lang":"eng"}],"year":"2013","place":"Berlin, Heidelberg","_id":"10902","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","type":"conference","volume":7810,"page":"214-225","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783642370649"],"isbn":["9783642370632"]},"citation":{"chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Sasha Rubin. “How to Travel between Languages.” In <i>7th International Conference on Language and Automata Theory and Applications</i>, 7810:214–25. LNCS. Berlin, Heidelberg: Springer Nature, 2013. <a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">https://doi.org/10.1007/978-3-642-37064-9_20</a>.","ieee":"K. Chatterjee, S. Chaubal, and S. Rubin, “How to travel between languages,” in <i>7th International Conference on Language and Automata Theory and Applications</i>, Bilbao, Spain, 2013, vol. 7810, pp. 214–225.","apa":"Chatterjee, K., Chaubal, S., &#38; Rubin, S. (2013). How to travel between languages. In <i>7th International Conference on Language and Automata Theory and Applications</i> (Vol. 7810, pp. 214–225). Berlin, Heidelberg: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">https://doi.org/10.1007/978-3-642-37064-9_20</a>","ama":"Chatterjee K, Chaubal S, Rubin S. How to travel between languages. In: <i>7th International Conference on Language and Automata Theory and Applications</i>. Vol 7810. LNCS. Berlin, Heidelberg: Springer Nature; 2013:214-225. doi:<a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">10.1007/978-3-642-37064-9_20</a>","ista":"Chatterjee K, Chaubal S, Rubin S. 2013. How to travel between languages. 7th International Conference on Language and Automata Theory and Applications. LATA: Conference on Language and Automata Theory and ApplicationsLNCS, LNCS, vol. 7810, 214–225.","mla":"Chatterjee, Krishnendu, et al. “How to Travel between Languages.” <i>7th International Conference on Language and Automata Theory and Applications</i>, vol. 7810, Springer Nature, 2013, pp. 214–25, doi:<a href=\"https://doi.org/10.1007/978-3-642-37064-9_20\">10.1007/978-3-642-37064-9_20</a>.","short":"K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg, 2013, pp. 214–225."},"status":"public","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. Thanks to Gabriele Puppis for suggesting the problem of identifying a deterministic transducer to compute the optimal cost, and to Martin Chmelik for his comments on the introduction."},{"citation":{"ama":"Reiter J, Božić I, Chatterjee K, Nowak M. TTP: Tool for tumor progression. In: <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>. Vol 8044. Lecture Notes in Computer Science. Springer; 2013:101-106. doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">10.1007/978-3-642-39799-8_6</a>","ista":"Reiter J, Božić I, Chatterjee K, Nowak M. 2013. TTP: Tool for tumor progression. Proceedings of 25th Int. Conf. on Computer Aided Verification. CAV: Computer Aided VerificationLecture Notes in Computer Science, LNCS, vol. 8044, 101–106.","short":"J. Reiter, I. Božić, K. Chatterjee, M. Nowak, in:, Proceedings of 25th Int. Conf. on Computer Aided Verification, Springer, 2013, pp. 101–106.","mla":"Reiter, Johannes, et al. “TTP: Tool for Tumor Progression.” <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, vol. 8044, Springer, 2013, pp. 101–06, doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">10.1007/978-3-642-39799-8_6</a>.","ieee":"J. Reiter, I. Božić, K. Chatterjee, and M. Nowak, “TTP: Tool for tumor progression,” in <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, St. Petersburg, Russia, 2013, vol. 8044, pp. 101–106.","chicago":"Reiter, Johannes, Ivana Božić, Krishnendu Chatterjee, and Martin Nowak. “TTP: Tool for Tumor Progression.” In <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, 8044:101–6. Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">https://doi.org/10.1007/978-3-642-39799-8_6</a>.","apa":"Reiter, J., Božić, I., Chatterjee, K., &#38; Nowak, M. (2013). TTP: Tool for tumor progression. In <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i> (Vol. 8044, pp. 101–106). St. Petersburg, Russia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">https://doi.org/10.1007/978-3-642-39799-8_6</a>"},"status":"public","oa":1,"external_id":{"arxiv":["1303.5251"]},"_id":"2000","year":"2013","volume":8044,"page":"101 - 106","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","abstract":[{"text":"In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics.","lang":"eng"}],"series_title":"Lecture Notes in Computer Science","arxiv":1,"date_created":"2018-12-11T11:55:08Z","ec_funded":1,"oa_version":"Preprint","publist_id":"5077","publication":"Proceedings of 25th Int. Conf. on Computer Aided Verification","title":"TTP: Tool for tumor progression","department":[{"_id":"KrCh"}],"publisher":"Springer","month":"01","language":[{"iso":"eng"}],"project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"day":"01","intvolume":"      8044","main_file_link":[{"url":"https://arxiv.org/abs/1303.5251","open_access":"1"}],"publication_status":"published","scopus_import":1,"quality_controlled":"1","date_published":"2013-01-01T00:00:00Z","author":[{"full_name":"Reiter, Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","first_name":"Johannes","orcid":"0000-0002-0170-7353","last_name":"Reiter"},{"full_name":"Božić, Ivana","first_name":"Ivana","last_name":"Božić"},{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"alternative_title":["LNCS"],"date_updated":"2023-09-07T11:40:43Z","doi":"10.1007/978-3-642-39799-8_6","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5399"},{"id":"1400","relation":"dissertation_contains","status":"public"}]},"conference":{"end_date":"2013-07-19","name":"CAV: Computer Aided Verification","start_date":"2013-07-13","location":"St. Petersburg, Russia"}},{"series_title":"Lecture Notes in Computer Science","abstract":[{"lang":"eng","text":"We study the problem of achieving a given value in Markov decision processes (MDPs) with several independent discounted reward objectives. We consider a generalised version of discounted reward objectives, in which the amount of discounting depends on the states visited and on the objective. This definition extends the usual definition of discounted reward, and allows to capture the systems in which the value of different commodities diminish at different and variable rates.\r\n\r\nWe establish results for two prominent subclasses of the problem, namely state-discount models where the discount factors are only dependent on the state of the MDP (and independent of the objective), and reward-discount models where they are only dependent on the objective (but not on the state of the MDP). For the state-discount models we use a straightforward reduction to expected total reward and show that the problem whether a value is achievable can be solved in polynomial time. For the reward-discount model we show that memory and randomisation of the strategies are required, but nevertheless that the problem is decidable and it is sufficient to consider strategies which after a certain number of steps behave in a memoryless way.\r\n\r\nFor the general case, we show that when restricted to graphs (i.e. MDPs with no randomisation), pure strategies and discount factors of the form 1/n where n is an integer, the problem is in PSPACE and finite memory suffices for achieving a given value. We also show that when the discount factors are not of the form 1/n, the memory required by a strategy can be infinite.\r\n"}],"publist_id":"4723","oa_version":"None","ec_funded":1,"date_created":"2018-12-11T11:56:30Z","publisher":"Springer","title":"Multi-objective discounted reward verification in graphs and MDPs","department":[{"_id":"KrCh"}],"citation":{"apa":"Chatterjee, K., Forejt, V., &#38; Wojtczak, D. (2013). Multi-objective discounted reward verification in graphs and MDPs. Presented at the LPAR: Logic for Programming, Artificial Intelligence, and Reasoning, Stellenbosch, South Africa: Springer. <a href=\"https://doi.org/10.1007/978-3-642-45221-5_17\">https://doi.org/10.1007/978-3-642-45221-5_17</a>","ieee":"K. Chatterjee, V. Forejt, and D. Wojtczak, “Multi-objective discounted reward verification in graphs and MDPs,” vol. 8312. Springer, pp. 228–242, 2013.","chicago":"Chatterjee, Krishnendu, Vojtěch Forejt, and Dominik Wojtczak. “Multi-Objective Discounted Reward Verification in Graphs and MDPs.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-45221-5_17\">https://doi.org/10.1007/978-3-642-45221-5_17</a>.","short":"K. Chatterjee, V. Forejt, D. Wojtczak, 8312 (2013) 228–242.","ista":"Chatterjee K, Forejt V, Wojtczak D. 2013. Multi-objective discounted reward verification in graphs and MDPs. 8312, 228–242.","mla":"Chatterjee, Krishnendu, et al. <i>Multi-Objective Discounted Reward Verification in Graphs and MDPs</i>. Vol. 8312, Springer, 2013, pp. 228–42, doi:<a href=\"https://doi.org/10.1007/978-3-642-45221-5_17\">10.1007/978-3-642-45221-5_17</a>.","ama":"Chatterjee K, Forejt V, Wojtczak D. Multi-objective discounted reward verification in graphs and MDPs. 2013;8312:228-242. doi:<a href=\"https://doi.org/10.1007/978-3-642-45221-5_17\">10.1007/978-3-642-45221-5_17</a>"},"status":"public","year":"2013","_id":"2238","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"228 - 242","volume":8312,"quality_controlled":"1","scopus_import":1,"alternative_title":["LNCS"],"doi":"10.1007/978-3-642-45221-5_17","date_updated":"2020-08-11T10:09:42Z","date_published":"2013-12-01T00:00:00Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Forejt, Vojtěch","last_name":"Forejt","first_name":"Vojtěch"},{"full_name":"Wojtczak, Dominik","last_name":"Wojtczak","first_name":"Dominik"}],"conference":{"name":"LPAR: Logic for Programming, Artificial Intelligence, and Reasoning","end_date":"2013-12-19","location":"Stellenbosch, South Africa","start_date":"2013-12-14"},"language":[{"iso":"eng"}],"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"month":"12","day":"01","publication_status":"published","intvolume":"      8312"},{"ddc":["000"],"day":"12","month":"12","project":[{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T10:11:15Z","date_updated":"2020-07-14T12:45:34Z","file_id":"4868","file_size":1050042,"checksum":"808e8b9e6e89658bee4ffbbfac1bd19d","file_name":"IST-2016-409-v1+1_journal.pone.0080814.pdf"}],"publication_status":"published","intvolume":"         8","doi":"10.1371/journal.pone.0080814","related_material":{"record":[{"id":"9749","status":"public","relation":"research_data"},{"status":"public","relation":"dissertation_contains","id":"1400"}]},"date_updated":"2023-09-07T11:40:43Z","pubrep_id":"409","author":[{"first_name":"Benjamin","last_name":"Zagorsky","full_name":"Zagorsky, Benjamin"},{"orcid":"0000-0002-0170-7353","last_name":"Reiter","first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","full_name":"Reiter, Johannes"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"date_published":"2013-12-12T00:00:00Z","quality_controlled":"1","scopus_import":1,"article_number":"e80814","file_date_updated":"2020-07-14T12:45:34Z","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"},"issue":"12","status":"public","oa":1,"citation":{"ama":"Zagorsky B, Reiter J, Chatterjee K, Nowak M. Forgiver triumphs in alternating prisoner’s dilemma . <i>PLoS One</i>. 2013;8(12). doi:<a href=\"https://doi.org/10.1371/journal.pone.0080814\">10.1371/journal.pone.0080814</a>","short":"B. Zagorsky, J. Reiter, K. Chatterjee, M. Nowak, PLoS One 8 (2013).","ista":"Zagorsky B, Reiter J, Chatterjee K, Nowak M. 2013. Forgiver triumphs in alternating prisoner’s dilemma . PLoS One. 8(12), e80814.","mla":"Zagorsky, Benjamin, et al. “Forgiver Triumphs in Alternating Prisoner’s Dilemma .” <i>PLoS One</i>, vol. 8, no. 12, e80814, Public Library of Science, 2013, doi:<a href=\"https://doi.org/10.1371/journal.pone.0080814\">10.1371/journal.pone.0080814</a>.","ieee":"B. Zagorsky, J. Reiter, K. Chatterjee, and M. Nowak, “Forgiver triumphs in alternating prisoner’s dilemma ,” <i>PLoS One</i>, vol. 8, no. 12. Public Library of Science, 2013.","chicago":"Zagorsky, Benjamin, Johannes Reiter, Krishnendu Chatterjee, and Martin Nowak. “Forgiver Triumphs in Alternating Prisoner’s Dilemma .” <i>PLoS One</i>. Public Library of Science, 2013. <a href=\"https://doi.org/10.1371/journal.pone.0080814\">https://doi.org/10.1371/journal.pone.0080814</a>.","apa":"Zagorsky, B., Reiter, J., Chatterjee, K., &#38; Nowak, M. (2013). Forgiver triumphs in alternating prisoner’s dilemma . <i>PLoS One</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0080814\">https://doi.org/10.1371/journal.pone.0080814</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","volume":8,"has_accepted_license":"1","year":"2013","_id":"2247","abstract":[{"lang":"eng","text":"Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise."}],"publisher":"Public Library of Science","publication":"PLoS One","title":"Forgiver triumphs in alternating prisoner's dilemma ","department":[{"_id":"KrCh"}],"publist_id":"4702","date_created":"2018-12-11T11:56:33Z","ec_funded":1,"oa_version":"Published Version"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","volume":8172,"page":"118 - 132","year":"2013","_id":"2279","oa":1,"status":"public","acknowledgement":"279307; ERC; Fonds National de la Reserche Luxembourg;  279499; ERC; Fonds National de la Reserche Luxembourg","citation":{"ieee":"K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” vol. 8172. Springer, pp. 118–132, 2013.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-319-02444-8_10\">https://doi.org/10.1007/978-3-319-02444-8_10</a>.","apa":"Chatterjee, K., Doyen, L., Randour, M., &#38; Raskin, J. (2013). Looking at mean-payoff and total-payoff through windows. Presented at the ATVA: Automated Technology for Verification and Analysis, Hanoi, Vietnam: Springer. <a href=\"https://doi.org/10.1007/978-3-319-02444-8_10\">https://doi.org/10.1007/978-3-319-02444-8_10</a>","ama":"Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. 2013;8172:118-132. doi:<a href=\"https://doi.org/10.1007/978-3-319-02444-8_10\">10.1007/978-3-319-02444-8_10</a>","short":"K. Chatterjee, L. Doyen, M. Randour, J. Raskin, 8172 (2013) 118–132.","ista":"Chatterjee K, Doyen L, Randour M, Raskin J. 2013. Looking at mean-payoff and total-payoff through windows. 8172, 118–132.","mla":"Chatterjee, Krishnendu, et al. <i>Looking at Mean-Payoff and Total-Payoff through Windows</i>. Vol. 8172, Springer, 2013, pp. 118–32, doi:<a href=\"https://doi.org/10.1007/978-3-319-02444-8_10\">10.1007/978-3-319-02444-8_10</a>."},"publisher":"Springer","title":"Looking at mean-payoff and total-payoff through windows","department":[{"_id":"KrCh"}],"publist_id":"4656","ec_funded":1,"date_created":"2018-12-11T11:56:44Z","oa_version":"Preprint","series_title":"Lecture Notes in Computer Science","abstract":[{"text":"We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.","lang":"eng"}],"publication_status":"published","intvolume":"      8172","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1302.4248"}],"day":"01","month":"01","language":[{"iso":"eng"}],"project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7"}],"conference":{"location":"Hanoi, Vietnam","start_date":"2013-10-15","name":"ATVA: Automated Technology for Verification and Analysis","end_date":"2013-10-18"},"alternative_title":["LNCS"],"date_updated":"2023-02-23T12:22:51Z","doi":"10.1007/978-3-319-02444-8_10","related_material":{"record":[{"id":"523","relation":"later_version","status":"public"}]},"date_published":"2013-01-01T00:00:00Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"last_name":"Randour","first_name":"Mickael","full_name":"Randour, Mickael"},{"last_name":"Raskin","first_name":"Jean","full_name":"Raskin, Jean"}],"quality_controlled":"1","scopus_import":1},{"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-642-40312-5"]},"month":"08","citation":{"apa":"Chatterjee, K., &#38; Sgall, J. (Eds.). (2013). <i>Mathematical Foundations of Computer Science 2013</i> (Vol. 8087, p. VI-854). Presented at the MFCS: Mathematical Foundations of Computer Science, Klosterneuburg, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-642-40313-2\">https://doi.org/10.1007/978-3-642-40313-2</a>","chicago":"Chatterjee, Krishnendu, and Jiri Sgall, eds. <i>Mathematical Foundations of Computer Science 2013</i>. Vol. 8087. Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-40313-2\">https://doi.org/10.1007/978-3-642-40313-2</a>.","ieee":"K. Chatterjee and J. Sgall, Eds., <i>Mathematical Foundations of Computer Science 2013</i>, vol. 8087. Springer, 2013, p. VI-854.","short":"K. Chatterjee, J. Sgall, eds., Mathematical Foundations of Computer Science 2013, Springer, 2013.","mla":"Chatterjee, Krishnendu, and Jiri Sgall, editors. <i>Mathematical Foundations of Computer Science 2013</i>. Vol. 8087, Springer, 2013, p. VI-854, doi:<a href=\"https://doi.org/10.1007/978-3-642-40313-2\">10.1007/978-3-642-40313-2</a>.","ista":"Chatterjee K, Sgall J eds. 2013. Mathematical Foundations of Computer Science 2013, Springer,p.","ama":"Chatterjee K, Sgall J, eds. <i>Mathematical Foundations of Computer Science 2013</i>. Vol 8087. Springer; 2013:VI-854. doi:<a href=\"https://doi.org/10.1007/978-3-642-40313-2\">10.1007/978-3-642-40313-2</a>"},"day":"08","status":"public","publication_status":"published","year":"2013","_id":"2292","intvolume":"      8087","type":"conference_editor","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"VI - 854","volume":8087,"quality_controlled":"1","series_title":"Lecture Notes in Computer Science","abstract":[{"text":"This book constitutes the thoroughly refereed conference proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, held in Klosterneuburg, Austria, in August 2013. The 67 revised full papers presented together with six invited talks were carefully selected from 191 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.","lang":"eng"}],"scopus_import":1,"date_updated":"2020-08-11T10:09:45Z","doi":"10.1007/978-3-642-40313-2","alternative_title":["LNCS"],"editor":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Jiri","last_name":"Sgall","full_name":"Sgall, Jiri"}],"date_published":"2013-08-08T00:00:00Z","publist_id":"4636","oa_version":"None","conference":{"start_date":"2013-08-26","location":"Klosterneuburg, Austria","end_date":"2013-08-30","name":"MFCS: Mathematical Foundations of Computer Science"},"date_created":"2018-12-11T11:56:48Z","publisher":"Springer","department":[{"_id":"KrCh"}],"title":"Mathematical Foundations of Computer Science 2013"},{"series_title":"Leibniz International Proceedings in Informatics","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal EXPTIME-complete complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite-memory strategies. We also establish asymptotically optimal (exponential) memory bounds.","lang":"eng"}],"publist_id":"4633","oa_version":"Published Version","date_created":"2018-12-11T11:56:50Z","ec_funded":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"}],"title":"What is decidable about partially observable Markov decision processes with omega-regular objectives","citation":{"apa":"Chatterjee, K., Chmelik, M., &#38; Tracol, M. (2013). What is decidable about partially observable Markov decision processes with omega-regular objectives. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.165\">https://doi.org/10.4230/LIPIcs.CSL.2013.165</a>","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.165\">https://doi.org/10.4230/LIPIcs.CSL.2013.165</a>.","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially observable Markov decision processes with omega-regular objectives,” vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 165–180, 2013.","mla":"Chatterjee, Krishnendu, et al. <i>What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives</i>. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 165–80, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.165\">10.4230/LIPIcs.CSL.2013.165</a>.","ista":"Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with omega-regular objectives. 23, 165–180.","short":"K. Chatterjee, M. Chmelik, M. Tracol, 23 (2013) 165–180.","ama":"Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable Markov decision processes with omega-regular objectives. 2013;23:165-180. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.165\">10.4230/LIPIcs.CSL.2013.165</a>"},"status":"public","oa":1,"year":"2013","has_accepted_license":"1","_id":"2295","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"165 - 180","volume":23,"quality_controlled":"1","scopus_import":1,"alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.CSL.2013.165","related_material":{"record":[{"relation":"later_version","status":"public","id":"1477"},{"id":"5400","relation":"earlier_version","status":"public"}]},"date_updated":"2023-02-23T12:24:38Z","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin"},{"last_name":"Tracol","first_name":"Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","full_name":"Tracol, Mathieu"}],"date_published":"2013-08-27T00:00:00Z","pubrep_id":"756","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"},"conference":{"location":"Torino, Italy","start_date":"2013-09-02","name":"CSL: Computer Science Logic","end_date":"2013-09-05"},"file_date_updated":"2020-07-14T12:45:37Z","project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory"},{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"language":[{"iso":"eng"}],"month":"08","day":"27","ddc":["000"],"publication_status":"published","file":[{"checksum":"ba2828322955574d9283bea0e17a37a6","file_name":"IST-2017-756-v1+1_2.pdf","file_size":345171,"date_updated":"2020-07-14T12:45:37Z","file_id":"4766","date_created":"2018-12-12T10:09:42Z","content_type":"application/pdf","access_level":"open_access","creator":"system","relation":"main_file"}],"intvolume":"        23"},{"publisher":"Springer","publication":"International Journal on Software Tools for Technology Transfer","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Synthesis of AMBA AHB from formal specification: A case study","publist_id":"4629","date_created":"2018-12-11T11:56:51Z","oa_version":"Submitted Version","abstract":[{"text":"The standard hardware design flow involves: (a) design of an integrated circuit using a hardware description language, (b) extensive functional and formal verification, and (c) logical synthesis. However, the above-mentioned processes consume significant effort and time. An alternative approach is to use a formal specification language as a high-level hardware description language and synthesize hardware from formal specifications. Our work is a case study of the synthesis of the widely and industrially used AMBA AHB protocol from formal specifications. Bloem et al. presented the first formal specifications for the AMBA AHB Arbiter and synthesized the AHB Arbiter circuit. However, in the first formal specification some important assumptions were missing. Our contributions are as follows: (a) We present detailed formal specifications for the AHB Arbiter incorporating the missing details, and obtain significant improvements in the synthesis results (both with respect to the number of gates in the synthesized circuit and with respect to the time taken to synthesize the circuit), and (b) we present formal specifications to generate compact circuits for the remaining two main components of AMBA AHB, namely, AHB Master and AHB Slave. Thus with systematic description we are able to automatically and completely synthesize an important and widely used industrial protocol.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","volume":15,"page":"585 - 601","year":"2013","has_accepted_license":"1","_id":"2299","issue":"5-6","oa":1,"status":"public","citation":{"apa":"Godhal, Y., Chatterjee, K., &#38; Henzinger, T. A. (2013). Synthesis of AMBA AHB from formal specification: A case study. <i>International Journal on Software Tools for Technology Transfer</i>. Springer. <a href=\"https://doi.org/10.1007/s10009-011-0207-9\">https://doi.org/10.1007/s10009-011-0207-9</a>","ieee":"Y. Godhal, K. Chatterjee, and T. A. Henzinger, “Synthesis of AMBA AHB from formal specification: A case study,” <i>International Journal on Software Tools for Technology Transfer</i>, vol. 15, no. 5–6. Springer, pp. 585–601, 2013.","chicago":"Godhal, Yashdeep, Krishnendu Chatterjee, and Thomas A Henzinger. “Synthesis of AMBA AHB from Formal Specification: A Case Study.” <i>International Journal on Software Tools for Technology Transfer</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s10009-011-0207-9\">https://doi.org/10.1007/s10009-011-0207-9</a>.","mla":"Godhal, Yashdeep, et al. “Synthesis of AMBA AHB from Formal Specification: A Case Study.” <i>International Journal on Software Tools for Technology Transfer</i>, vol. 15, no. 5–6, Springer, 2013, pp. 585–601, doi:<a href=\"https://doi.org/10.1007/s10009-011-0207-9\">10.1007/s10009-011-0207-9</a>.","short":"Y. Godhal, K. Chatterjee, T.A. Henzinger, International Journal on Software Tools for Technology Transfer 15 (2013) 585–601.","ista":"Godhal Y, Chatterjee K, Henzinger TA. 2013. Synthesis of AMBA AHB from formal specification: A case study. International Journal on Software Tools for Technology Transfer. 15(5–6), 585–601.","ama":"Godhal Y, Chatterjee K, Henzinger TA. Synthesis of AMBA AHB from formal specification: A case study. <i>International Journal on Software Tools for Technology Transfer</i>. 2013;15(5-6):585-601. doi:<a href=\"https://doi.org/10.1007/s10009-011-0207-9\">10.1007/s10009-011-0207-9</a>"},"file_date_updated":"2020-07-14T12:45:37Z","doi":"10.1007/s10009-011-0207-9","date_updated":"2021-01-12T06:56:37Z","pubrep_id":"87","date_published":"2013-10-01T00:00:00Z","author":[{"last_name":"Godhal","first_name":"Yashdeep","id":"5B547124-EB61-11E9-8887-89D9C04DBDF5","full_name":"Godhal, Yashdeep"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A"}],"quality_controlled":"1","scopus_import":1,"file":[{"file_size":277372,"checksum":"57b06a732dd8d6349190dba6b5b0d33b","file_name":"IST-2012-87-v1+1_Synthesis_of_AMBA_AHB_from_formal_specifications-_A_case_study.pdf","date_updated":"2020-07-14T12:45:37Z","file_id":"4910","content_type":"application/pdf","date_created":"2018-12-12T10:11:53Z","relation":"main_file","access_level":"open_access","creator":"system"}],"publication_status":"published","intvolume":"        15","ddc":["000"],"day":"01","month":"10","language":[{"iso":"eng"}],"project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}]},{"month":"08","language":[{"iso":"eng"}],"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"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"}],"day":"01","publication_status":"published","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1305.4103"}],"quality_controlled":"1","scopus_import":1,"doi":"10.1109/LICS.2013.39","date_updated":"2023-09-20T11:15:30Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"1294"}]},"date_published":"2013-08-01T00:00:00Z","author":[{"full_name":"Brázdil, Tomáš","last_name":"Brázdil","first_name":"Tomáš"},{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Forejt","first_name":"Vojtěch","full_name":"Forejt, Vojtěch"},{"full_name":"Kučera, Antonín","last_name":"Kučera","first_name":"Antonín"}],"conference":{"location":"New Orleans, LA, United States","start_date":"2013-06-25","name":"LICS: Logic in Computer Science","end_date":"2013-06-28"},"citation":{"chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Trading Performance for Stability in Markov Decision Processes.” In <i>28th Annual ACM/IEEE Symposium</i>, 331–40. IEEE, 2013. <a href=\"https://doi.org/10.1109/LICS.2013.39\">https://doi.org/10.1109/LICS.2013.39</a>.","ieee":"T. Brázdil, K. Chatterjee, V. Forejt, and A. Kučera, “Trading performance for stability in Markov decision processes,” in <i>28th Annual ACM/IEEE Symposium</i>, New Orleans, LA, United States, 2013, pp. 331–340.","apa":"Brázdil, T., Chatterjee, K., Forejt, V., &#38; Kučera, A. (2013). Trading performance for stability in Markov decision processes. In <i>28th Annual ACM/IEEE Symposium</i> (pp. 331–340). New Orleans, LA, United States: IEEE. <a href=\"https://doi.org/10.1109/LICS.2013.39\">https://doi.org/10.1109/LICS.2013.39</a>","ama":"Brázdil T, Chatterjee K, Forejt V, Kučera A. Trading performance for stability in Markov decision processes. In: <i>28th Annual ACM/IEEE Symposium</i>. IEEE; 2013:331-340. doi:<a href=\"https://doi.org/10.1109/LICS.2013.39\">10.1109/LICS.2013.39</a>","short":"T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, in:, 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–340.","ista":"Brázdil T, Chatterjee K, Forejt V, Kučera A. 2013. Trading performance for stability in Markov decision processes. 28th Annual ACM/IEEE Symposium. LICS: Logic in Computer Science, 331–340.","mla":"Brázdil, Tomáš, et al. “Trading Performance for Stability in Markov Decision Processes.” <i>28th Annual ACM/IEEE Symposium</i>, IEEE, 2013, pp. 331–40, doi:<a href=\"https://doi.org/10.1109/LICS.2013.39\">10.1109/LICS.2013.39</a>."},"external_id":{"arxiv":["1305.4103"]},"oa":1,"status":"public","year":"2013","_id":"2305","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","page":"331 - 340","abstract":[{"lang":"eng","text":"We study the complexity of central controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize both the expected mean-payoff performance of the system and its stability. e argue that the basic theoretical notion of expressing the stability in terms of the variance of the mean-payoff (called global variance in our paper) is not always sufficient, since it ignores possible instabilities on respective runs. For this reason we propose alernative definitions of stability, which we call local and hybrid variance, and which express how rewards on each run deviate from the run's own mean-payoff and from the expected mean-payoff, respectively. We show that a strategy ensuring both the expected mean-payoff and the variance below given bounds requires randomization and memory, under all the above semantics of variance. We then look at the problem of determining whether there is a such a strategy. For the global variance, we show that the problem is in PSPACE, and that the answer can be approximated in pseudo-polynomial time. For the hybrid variance, the analogous decision problem is in NP, and a polynomial-time approximating algorithm also exists. For local variance, we show that the decision problem is in NP. Since the overall performance can be traded for stability (and vice versa), we also present algorithms for approximating the associated Pareto curve in all the three cases. Finally, we study a special case of the decision problems, where we require a given expected mean-payoff together with zero variance. Here we show that the problems can be all solved in polynomial time."}],"arxiv":1,"publist_id":"4622","date_created":"2018-12-11T11:56:53Z","ec_funded":1,"oa_version":"Preprint","publisher":"IEEE","publication":"28th Annual ACM/IEEE Symposium","title":"Trading performance for stability in Markov decision processes","department":[{"_id":"KrCh"}]},{"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Yaron","last_name":"Velner","full_name":"Velner, Yaron"}],"date_published":"2013-08-01T00:00:00Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"717"}]},"date_updated":"2023-02-23T13:00:42Z","doi":"10.1007/978-3-642-40184-8_35","alternative_title":["LNCS"],"scopus_import":1,"quality_controlled":"1","conference":{"name":"CONCUR: Concurrency Theory","end_date":"2013-08-30","location":"Buenos Aires, Argentinia","start_date":"2013-08-27"},"day":"01","month":"08","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"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1210.3141"}],"intvolume":"      8052","publication_status":"published","arxiv":1,"abstract":[{"text":"Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work, we consider both finite-state game graphs, and recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion. The objectives we study are multidimensional mean-payoff objectives, where the goal of player 1 is to ensure that the mean-payoff is non-negative in all dimensions. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation. Our main contributions are as follows: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of the weights are fixed; whereas if the number of dimensions is arbitrary, then the problem is known to be coNP-complete. (2) We show that pushdown graphs with multidimensional mean-payoff objectives can be solved in polynomial time. For both (1) and (2) our algorithms are based on hyperplane separation technique. (3) For pushdown games under global strategies both one and multidimensional mean-payoff objectives problems are known to be undecidable, and we show that under modular strategies the multidimensional problem is also undecidable; under modular strategies the one-dimensional problem is NP-complete. We show that if the number of modules, the number of exits, and the maximal absolute value of the weights are fixed, then pushdown games under modular strategies with one-dimensional mean-payoff objectives can be solved in polynomial time, and if either the number of exits or the number of modules is unbounded, then the problem is NP-hard. (4) Finally we show that a fixed parameter tractable algorithm for finite-state multidimensional mean-payoff games or pushdown games under modular strategies with one-dimensional mean-payoff objectives would imply the fixed parameter tractability of parity games.","lang":"eng"}],"series_title":"Lecture Notes in Computer Science","title":"Hyperplane separation technique for multidimensional mean-payoff games","department":[{"_id":"KrCh"}],"publisher":"Springer","ec_funded":1,"date_created":"2018-12-11T11:57:01Z","oa_version":"Preprint","publist_id":"4597","status":"public","oa":1,"external_id":{"arxiv":["1210.3141"]},"citation":{"apa":"Chatterjee, K., &#38; Velner, Y. (2013). Hyperplane separation technique for multidimensional mean-payoff games. Presented at the CONCUR: Concurrency Theory, Buenos Aires, Argentinia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-40184-8_35\">https://doi.org/10.1007/978-3-642-40184-8_35</a>","ieee":"K. Chatterjee and Y. Velner, “Hyperplane separation technique for multidimensional mean-payoff games,” vol. 8052. Springer, pp. 500–515, 2013.","chicago":"Chatterjee, Krishnendu, and Yaron Velner. “Hyperplane Separation Technique for Multidimensional Mean-Payoff Games.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-40184-8_35\">https://doi.org/10.1007/978-3-642-40184-8_35</a>.","ista":"Chatterjee K, Velner Y. 2013. Hyperplane separation technique for multidimensional mean-payoff games. 8052, 500–515.","mla":"Chatterjee, Krishnendu, and Yaron Velner. <i>Hyperplane Separation Technique for Multidimensional Mean-Payoff Games</i>. Vol. 8052, Springer, 2013, pp. 500–15, doi:<a href=\"https://doi.org/10.1007/978-3-642-40184-8_35\">10.1007/978-3-642-40184-8_35</a>.","short":"K. Chatterjee, Y. Velner, 8052 (2013) 500–515.","ama":"Chatterjee K, Velner Y. Hyperplane separation technique for multidimensional mean-payoff games. 2013;8052:500-515. doi:<a href=\"https://doi.org/10.1007/978-3-642-40184-8_35\">10.1007/978-3-642-40184-8_35</a>"},"volume":8052,"page":"500 - 515","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","_id":"2329","year":"2013"},{"oa_version":"Published Version","date_created":"2018-12-12T11:39:07Z","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:44Z","title":"TTP: Tool for Tumor Progression","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics."}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"2000"}]},"doi":"10.15479/AT:IST-2013-104-v1-1","date_updated":"2023-02-23T10:23:57Z","alternative_title":["IST Austria Technical Report"],"author":[{"first_name":"Johannes","last_name":"Reiter","orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Bozic","first_name":"Ivana","full_name":"Bozic, Ivana"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"pubrep_id":"104","date_published":"2013-01-11T00:00:00Z","publication_status":"published","year":"2013","file":[{"relation":"main_file","access_level":"open_access","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:54:20Z","date_updated":"2020-07-14T12:46:44Z","file_id":"5542","file_size":1471954,"file_name":"IST-2013-104-v1+1_tumortool.pdf","checksum":"2cc8c6e157eca1271128db80bb3dec80"}],"has_accepted_license":"1","_id":"5399","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"17","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"month":"01","citation":{"mla":"Reiter, Johannes, et al. <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">10.15479/AT:IST-2013-104-v1-1</a>.","ista":"Reiter J, Bozic I, Chatterjee K, Nowak M. 2013. TTP: Tool for Tumor Progression, IST Austria, 17p.","short":"J. Reiter, I. Bozic, K. Chatterjee, M. Nowak, TTP: Tool for Tumor Progression, IST Austria, 2013.","ama":"Reiter J, Bozic I, Chatterjee K, Nowak M. <i>TTP: Tool for Tumor Progression</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">10.15479/AT:IST-2013-104-v1-1</a>","apa":"Reiter, J., Bozic, I., Chatterjee, K., &#38; Nowak, M. (2013). <i>TTP: Tool for Tumor Progression</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">https://doi.org/10.15479/AT:IST-2013-104-v1-1</a>","ieee":"J. Reiter, I. Bozic, K. Chatterjee, and M. Nowak, <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013.","chicago":"Reiter, Johannes, Ivana Bozic, Krishnendu Chatterjee, and Martin Nowak. <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">https://doi.org/10.15479/AT:IST-2013-104-v1-1</a>."},"day":"11","ddc":["000"],"oa":1,"status":"public"},{"alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2013-109-v1-1","date_updated":"2023-02-23T10:36:45Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"1477"},{"relation":"later_version","status":"public","id":"2295"}]},"pubrep_id":"109","date_published":"2013-02-20T00:00:00Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin"},{"id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","full_name":"Tracol, Mathieu","last_name":"Tracol","first_name":"Mathieu"}],"abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives."}],"publisher":"IST Austria","title":"What is decidable about partially observable Markov decision processes with ω-regular objectives","file_date_updated":"2020-07-14T12:46:44Z","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:07Z","oa_version":"Published Version","ddc":["000","005"],"day":"20","status":"public","oa":1,"month":"02","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"citation":{"apa":"Chatterjee, K., Chmelik, M., &#38; Tracol, M. (2013). <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>.","ista":"Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with ω-regular objectives, IST Austria, 41p.","mla":"Chatterjee, Krishnendu, et al. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">10.15479/AT:IST-2013-109-v1-1</a>.","short":"K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013.","ama":"Chatterjee K, Chmelik M, Tracol M. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">10.15479/AT:IST-2013-109-v1-1</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","page":"41","year":"2013","has_accepted_license":"1","file":[{"file_size":483407,"file_name":"IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf","checksum":"cbba40210788a1b22c6cf06433b5ed6f","file_id":"5467","date_updated":"2020-07-14T12:46:44Z","content_type":"application/pdf","date_created":"2018-12-12T11:53:06Z","relation":"main_file","access_level":"open_access","creator":"system"}],"publication_status":"published","_id":"5400"},{"_id":"5403","publication_status":"published","has_accepted_license":"1","year":"2013","file":[{"date_updated":"2020-07-14T12:46:45Z","file_id":"5510","file_size":434523,"checksum":"063868c665beec37bf28160e2a695746","file_name":"IST-2013-126-v1+1_soda_full.pdf","relation":"main_file","creator":"system","access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T11:53:49Z"}],"page":"33","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">10.15479/AT:IST-2013-126-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff games, IST Austria, 33p.","short":"K. Chatterjee, R. Ibsen-Jensen, Qualitative Analysis of Concurrent Mean-Payoff Games, IST Austria, 2013.","ama":"Chatterjee K, Ibsen-Jensen R. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">10.15479/AT:IST-2013-126-v1-1</a>","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2013). <i>Qualitative analysis of concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">https://doi.org/10.15479/AT:IST-2013-126-v1-1</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>Qualitative analysis of concurrent mean-payoff games</i>. IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">https://doi.org/10.15479/AT:IST-2013-126-v1-1</a>."},"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"month":"07","oa":1,"status":"public","day":"03","ddc":["000","005"],"oa_version":"Published Version","date_created":"2018-12-12T11:39:08Z","file_date_updated":"2020-07-14T12:46:45Z","department":[{"_id":"KrCh"}],"title":"Qualitative analysis of concurrent mean-payoff games","publisher":"IST Austria","abstract":[{"text":"We consider concurrent games played by two-players on a finite state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to every transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of mean-payoff games) that is not known to be in polynomial time.","lang":"eng"}],"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"}],"pubrep_id":"126","date_published":"2013-07-03T00:00:00Z","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:22:53Z","related_material":{"record":[{"id":"524","relation":"later_version","status":"public"}]},"doi":"10.15479/AT:IST-2013-126-v1-1"},{"page":"29","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","_id":"5404","has_accepted_license":"1","year":"2013","file":[{"file_id":"5496","date_updated":"2020-07-14T12:46:45Z","file_size":517275,"checksum":"79ee5e677a82611ce06e0360c69d494a","file_name":"IST-2013-127-v1+1_ergodic.pdf","relation":"main_file","creator":"system","access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T11:53:35Z"}],"publication_status":"published","status":"public","oa":1,"ddc":["000","005"],"day":"03","citation":{"ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The complexity of ergodic games</i>. IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">https://doi.org/10.15479/AT:IST-2013-127-v1-1</a>.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2013). <i>The complexity of ergodic games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">https://doi.org/10.15479/AT:IST-2013-127-v1-1</a>","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Complexity of Ergodic Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">10.15479/AT:IST-2013-127-v1-1</a>","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">10.15479/AT:IST-2013-127-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p.","short":"K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013."},"month":"07","publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:45Z","title":"The complexity of ergodic games","publisher":"IST Austria","date_created":"2018-12-12T11:39:08Z","oa_version":"Published Version","date_published":"2013-07-03T00:00:00Z","pubrep_id":"127","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"}],"alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T10:30:55Z","doi":"10.15479/AT:IST-2013-127-v1-1","related_material":{"record":[{"id":"2162","relation":"later_version","status":"public"}]},"abstract":[{"text":"We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games.","lang":"eng"}]}]