[{"_id":"2816","publist_id":"3985","oa_version":"Published Version","quality_controlled":"1","pubrep_id":"134","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"},"doi":"10.7554/eLife.00747","citation":{"apa":"Božić, I., Reiter, J., Allen, B., Antal, T., Chatterjee, K., Shah, P., … Nowak, M. (2013). Evolutionary dynamics of cancer in response to targeted combination therapy. <i>ELife</i>. eLife Sciences Publications. <a href=\"https://doi.org/10.7554/eLife.00747\">https://doi.org/10.7554/eLife.00747</a>","ista":"Božić I, Reiter J, Allen B, Antal T, Chatterjee K, Shah P, Moon Y, Yaqubie A, Kelly N, Le D, Lipson E, Chapman P, Diaz L, Vogelstein B, Nowak M. 2013. Evolutionary dynamics of cancer in response to targeted combination therapy. eLife. 2, e00747.","ama":"Božić I, Reiter J, Allen B, et al. Evolutionary dynamics of cancer in response to targeted combination therapy. <i>eLife</i>. 2013;2. doi:<a href=\"https://doi.org/10.7554/eLife.00747\">10.7554/eLife.00747</a>","mla":"Božić, Ivana, et al. “Evolutionary Dynamics of Cancer in Response to Targeted Combination Therapy.” <i>ELife</i>, vol. 2, e00747, eLife Sciences Publications, 2013, doi:<a href=\"https://doi.org/10.7554/eLife.00747\">10.7554/eLife.00747</a>.","ieee":"I. Božić <i>et al.</i>, “Evolutionary dynamics of cancer in response to targeted combination therapy,” <i>eLife</i>, vol. 2. eLife Sciences Publications, 2013.","short":"I. Božić, J. Reiter, B. Allen, T. Antal, K. Chatterjee, P. Shah, Y. Moon, A. Yaqubie, N. Kelly, D. Le, E. Lipson, P. Chapman, L. Diaz, B. Vogelstein, M. Nowak, ELife 2 (2013).","chicago":"Božić, Ivana, Johannes Reiter, Benjamin Allen, Tibor Antal, Krishnendu Chatterjee, Preya Shah, Yo Moon, et al. “Evolutionary Dynamics of Cancer in Response to Targeted Combination Therapy.” <i>ELife</i>. eLife Sciences Publications, 2013. <a href=\"https://doi.org/10.7554/eLife.00747\">https://doi.org/10.7554/eLife.00747</a>."},"department":[{"_id":"KrCh"}],"scopus_import":"1","volume":2,"title":"Evolutionary dynamics of cancer in response to targeted combination therapy","date_updated":"2026-07-29T10:15:25Z","author":[{"full_name":"Božić, Ivana","first_name":"Ivana","last_name":"Božić"},{"orcid":"0000-0002-0170-7353","last_name":"Reiter","first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","full_name":"Reiter, Johannes"},{"full_name":"Allen, Benjamin","first_name":"Benjamin","last_name":"Allen"},{"full_name":"Antal, Tibor","last_name":"Antal","first_name":"Tibor"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Preya","last_name":"Shah","full_name":"Shah, Preya"},{"full_name":"Moon, Yo","first_name":"Yo","last_name":"Moon"},{"full_name":"Yaqubie, Amin","first_name":"Amin","last_name":"Yaqubie"},{"last_name":"Kelly","first_name":"Nicole","full_name":"Kelly, Nicole"},{"last_name":"Le","first_name":"Dung","full_name":"Le, Dung"},{"full_name":"Lipson, Evan","first_name":"Evan","last_name":"Lipson"},{"last_name":"Chapman","first_name":"Paul","full_name":"Chapman, Paul"},{"full_name":"Diaz, Luis","first_name":"Luis","last_name":"Diaz"},{"full_name":"Vogelstein, Bert","last_name":"Vogelstein","first_name":"Bert"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"license":"https://creativecommons.org/licenses/by/4.0/","external_id":{"isi":["000328619300005"]},"day":"25","related_material":{"record":[{"status":"public","id":"1400","relation":"dissertation_contains"}]},"file_date_updated":"2020-07-14T12:45:49Z","publication":"eLife","ddc":["570","610"],"status":"public","month":"06","language":[{"iso":"eng"}],"intvolume":"         2","date_created":"2018-12-11T11:59:45Z","has_accepted_license":"1","abstract":[{"lang":"eng","text":"In solid tumors, targeted treatments can lead to dramatic regressions, but responses are often short-lived because resistant cancer cells arise. The major strategy proposed for overcoming resistance is combination therapy. We present a mathematical model describing the evolutionary dynamics of lesions in response to treatment. We first studied 20 melanoma patients receiving vemurafenib. We then applied our model to an independent set of pancreatic, colorectal, and melanoma cancer patients with metastatic disease. We find that dual therapy results in long-term disease control for most patients, if there are no single mutations that cause cross-resistance to both drugs; in patients with large disease burden, triple therapy is needed. We also find that simultaneous therapy with two drugs is much more effective than sequential therapy. Our results provide realistic expectations for the efficacy of new drug combinations and inform the design of trials for new cancer therapeutics."}],"publisher":"eLife Sciences Publications","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2013-06-25T00:00:00Z","article_number":"e00747","publication_status":"published","year":"2013","article_processing_charge":"No","file":[{"date_created":"2018-12-12T10:12:48Z","relation":"main_file","file_name":"IST-2013-134-v1+1_e00747.full.pdf","checksum":"2c38c47815eacd8fa66cb8b404cf7c61","creator":"system","file_size":3358321,"access_level":"open_access","content_type":"application/pdf","file_id":"4967","date_updated":"2020-07-14T12:45:49Z"}],"isi":1,"type":"journal_article","oa":1},{"alternative_title":["LNCS"],"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."}],"date_created":"2018-12-11T11:55:08Z","publisher":"Springer","language":[{"iso":"eng"}],"intvolume":"      8044","status":"public","month":"01","publication":"Proceedings of 25th Int. Conf. on Computer Aided Verification","page":"101 - 106","type":"conference","ec_funded":1,"oa":1,"year":"2013","publication_status":"published","series_title":"Lecture Notes in Computer Science","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2013-01-01T00:00:00Z","department":[{"_id":"KrCh"}],"scopus_import":1,"volume":8044,"project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"citation":{"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>.","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.","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.","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>","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>"},"doi":"10.1007/978-3-642-39799-8_6","publist_id":"5077","_id":"2000","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1303.5251"}],"quality_controlled":"1","oa_version":"Preprint","related_material":{"record":[{"relation":"earlier_version","id":"5399","status":"public"},{"relation":"dissertation_contains","id":"1400","status":"public"}]},"day":"01","arxiv":1,"conference":{"end_date":"2013-07-19","location":"St. Petersburg, Russia","name":"CAV: Computer Aided Verification","start_date":"2013-07-13"},"external_id":{"arxiv":["1303.5251"]},"author":[{"id":"4A918E98-F248-11E8-B48F-1D18A9856A87","full_name":"Reiter, Johannes","first_name":"Johannes","orcid":"0000-0002-0170-7353","last_name":"Reiter"},{"first_name":"Ivana","last_name":"Božić","full_name":"Božić, Ivana"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"date_updated":"2026-07-29T10:15:25Z","title":"TTP: Tool for tumor progression"},{"intvolume":"        18","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"has_accepted_license":"1","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning vertices from where the objective can be ensured with probability 1. We study for the first time the average case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, for the average case analysis over all MDPs we show that the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given that all MDPs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small."}],"date_created":"2018-12-11T11:59:13Z","month":"12","status":"public","ddc":["000"],"oa":1,"type":"conference","ec_funded":1,"page":"461 - 473","date_published":"2012-12-10T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file":[{"date_updated":"2020-07-14T12:45:45Z","file_id":"5040","file_size":519040,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T10:13:53Z","checksum":"d4d644ed1a885dbfc4fa1ef4c5724dab","file_name":"IST-2016-525-v1+1_42_1_.pdf","creator":"system"}],"year":"2012","publication_status":"published","tmp":{"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)","short":"CC BY-NC-ND (4.0)"},"doi":"10.4230/LIPIcs.FSTTCS.2012.461","citation":{"ista":"Chatterjee K, Joglekar M, Shah N. 2012. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18, 461–473.","ama":"Chatterjee K, Joglekar M, Shah N. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. In: Vol 18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:461-473. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461\">10.4230/LIPIcs.FSTTCS.2012.461</a>","apa":"Chatterjee, K., Joglekar, M., &#38; Shah, N. (2012). Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives (Vol. 18, pp. 461–473). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461\">https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461</a>","mla":"Chatterjee, Krishnendu, et al. <i>Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives</i>. Vol. 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–73, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461\">10.4230/LIPIcs.FSTTCS.2012.461</a>.","ieee":"K. Chatterjee, M. Joglekar, and N. Shah, “Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India, 2012, vol. 18, pp. 461–473.","short":"K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–473.","chicago":"Chatterjee, Krishnendu, Manas Joglekar, and Nisarg Shah. “Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives,” 18:461–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461\">https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461</a>."},"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"volume":18,"scopus_import":1,"department":[{"_id":"KrCh"}],"oa_version":"Published Version","quality_controlled":"1","publist_id":"4180","_id":"2715","pubrep_id":"525","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","conference":{"end_date":"2012-12-17","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","location":"Hyderabad, India","start_date":"2012-12-15"},"file_date_updated":"2020-07-14T12:45:45Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"1598"}]},"day":"10","date_updated":"2025-09-23T08:00:31Z","title":"Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Joglekar, Manas","first_name":"Manas","last_name":"Joglekar"},{"full_name":"Shah, Nisarg","first_name":"Nisarg","last_name":"Shah"}]},{"project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"citation":{"chicago":"Chatterjee, Krishnendu, Damien Zufferey, and Martin Nowak. “Evolutionary Game Dynamics in Populations with Different Learners.” <i>Journal of Theoretical Biology</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.jtbi.2012.02.021\">https://doi.org/10.1016/j.jtbi.2012.02.021</a>.","short":"K. Chatterjee, D. Zufferey, M. Nowak, Journal of Theoretical Biology 301 (2012) 161–173.","ieee":"K. Chatterjee, D. Zufferey, and M. Nowak, “Evolutionary game dynamics in populations with different learners,” <i>Journal of Theoretical Biology</i>, vol. 301. Elsevier, pp. 161–173, 2012.","mla":"Chatterjee, Krishnendu, et al. “Evolutionary Game Dynamics in Populations with Different Learners.” <i>Journal of Theoretical Biology</i>, vol. 301, Elsevier, 2012, pp. 161–73, doi:<a href=\"https://doi.org/10.1016/j.jtbi.2012.02.021\">10.1016/j.jtbi.2012.02.021</a>.","ama":"Chatterjee K, Zufferey D, Nowak M. Evolutionary game dynamics in populations with different learners. <i>Journal of Theoretical Biology</i>. 2012;301:161-173. doi:<a href=\"https://doi.org/10.1016/j.jtbi.2012.02.021\">10.1016/j.jtbi.2012.02.021</a>","ista":"Chatterjee K, Zufferey D, Nowak M. 2012. Evolutionary game dynamics in populations with different learners. Journal of Theoretical Biology. 301, 161–173.","apa":"Chatterjee, K., Zufferey, D., &#38; Nowak, M. (2012). Evolutionary game dynamics in populations with different learners. <i>Journal of Theoretical Biology</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jtbi.2012.02.021\">https://doi.org/10.1016/j.jtbi.2012.02.021</a>"},"doi":"10.1016/j.jtbi.2012.02.021","scopus_import":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"volume":301,"publist_id":"3946","_id":"2848","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3322297/","open_access":"1"}],"oa_version":"Submitted Version","quality_controlled":"1","external_id":{"pmid":["22394652"],"isi":["000303079500016"]},"day":"21","date_updated":"2025-09-30T08:20:22Z","title":"Evolutionary game dynamics in populations with different learners","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Zufferey","orcid":"0000-0002-3197-8736","first_name":"Damien","full_name":"Zufferey, Damien","id":"4397AC76-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"language":[{"iso":"eng"}],"intvolume":"       301","abstract":[{"lang":"eng","text":"We study evolutionary game theory in a setting where individuals learn from each other. We extend the traditional approach by assuming that a population contains individuals with different learning abilities. In particular, we explore the situation where individuals have different search spaces, when attempting to learn the strategies of others. The search space of an individual specifies the set of strategies learnable by that individual. The search space is genetically given and does not change under social evolutionary dynamics. We introduce a general framework and study a specific example in the context of direct reciprocity. For this example, we obtain the counter intuitive result that cooperation can only evolve for intermediate benefit-to-cost ratios, while small and large benefit-to-cost ratios favor defection. Our paper is a step toward making a connection between computational learning theory and evolutionary game dynamics."}],"pmid":1,"date_created":"2018-12-11T11:59:55Z","publisher":"Elsevier","corr_author":"1","status":"public","publication":"Journal of Theoretical Biology","month":"05","ec_funded":1,"type":"journal_article","isi":1,"oa":1,"page":"161 - 173","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2012-05-21T00:00:00Z","year":"2012","article_processing_charge":"No","publication_status":"published"},{"publisher":"EPTCS","abstract":[{"lang":"eng","text":"The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a quantitative measure for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intu- itively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, and that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies."}],"date_created":"2018-12-11T12:00:19Z","intvolume":"        96","language":[{"iso":"eng"}],"publication":"Electronic Proceedings in Theoretical Computer Science","status":"public","month":"10","page":"29 - 42","oa":1,"type":"conference","ec_funded":1,"publication_status":"published","year":"2012","date_published":"2012-10-07T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":96,"scopus_import":1,"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"doi":"10.4204/EPTCS.96.3","citation":{"short":"P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, 2012, pp. 29–42.","chicago":"Cerny, Pavol, Martin Chmelik, Thomas A Henzinger, and Arjun Radhakrishna. “Interface Simulation Distances.” In <i>Electronic Proceedings in Theoretical Computer Science</i>, 96:29–42. EPTCS, 2012. <a href=\"https://doi.org/10.4204/EPTCS.96.3\">https://doi.org/10.4204/EPTCS.96.3</a>.","ista":"Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. 2012. Interface Simulation Distances. Electronic Proceedings in Theoretical Computer Science. GandALF: Games, Automata, Logic, and Formal Verification vol. 96, 29–42.","ama":"Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. Interface Simulation Distances. In: <i>Electronic Proceedings in Theoretical Computer Science</i>. Vol 96. EPTCS; 2012:29-42. doi:<a href=\"https://doi.org/10.4204/EPTCS.96.3\">10.4204/EPTCS.96.3</a>","apa":"Cerny, P., Chmelik, M., Henzinger, T. A., &#38; Radhakrishna, A. (2012). Interface Simulation Distances. In <i>Electronic Proceedings in Theoretical Computer Science</i> (Vol. 96, pp. 29–42). Napoli, Italy: EPTCS. <a href=\"https://doi.org/10.4204/EPTCS.96.3\">https://doi.org/10.4204/EPTCS.96.3</a>","mla":"Cerny, Pavol, et al. “Interface Simulation Distances.” <i>Electronic Proceedings in Theoretical Computer Science</i>, vol. 96, EPTCS, 2012, pp. 29–42, doi:<a href=\"https://doi.org/10.4204/EPTCS.96.3\">10.4204/EPTCS.96.3</a>.","ieee":"P. Cerny, M. Chmelik, T. A. Henzinger, and A. Radhakrishna, “Interface Simulation Distances,” in <i>Electronic Proceedings in Theoretical Computer Science</i>, Napoli, Italy, 2012, vol. 96, pp. 29–42."},"project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa_version":"Submitted Version","main_file_link":[{"url":"http://arxiv.org/abs/1210.2450","open_access":"1"}],"_id":"2916","publist_id":"3827","arxiv":1,"day":"07","related_material":{"record":[{"status":"public","relation":"later_version","id":"1733"}]},"external_id":{"arxiv":["1210.2450"]},"conference":{"end_date":"2012-09-08","location":"Napoli, Italy","name":"GandALF: Games, Automata, Logic, and Formal Verification","start_date":"2012-09-06"},"author":[{"first_name":"Pavol","last_name":"Cerny","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger"},{"last_name":"Radhakrishna","first_name":"Arjun","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","full_name":"Radhakrishna, Arjun"}],"title":"Interface Simulation Distances","date_updated":"2025-09-29T13:14:24Z"},{"publication_status":"published","year":"2012","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2012-06-01T00:00:00Z","page":"385 - 399","type":"conference","ec_funded":1,"oa":1,"status":"public","month":"06","date_created":"2018-12-11T12:00:29Z","abstract":[{"text":"We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.","lang":"eng"}],"alternative_title":["LNCS"],"publisher":"Springer","language":[{"iso":"eng"}],"intvolume":"      7561","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Majumdar, Ritankar","first_name":"Ritankar","last_name":"Majumdar"}],"title":"Equivalence of games with probabilistic uncertainty and partial observation games","date_updated":"2025-07-10T11:52:24Z","day":"01","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","arxiv":1,"conference":{"start_date":"2012-10-03","location":"Thiruvananthapuram, India","name":"ATVA: Automated Technology for Verification and Analysis","end_date":"2012-10-06"},"external_id":{"arxiv":["1202.4140"]},"_id":"2947","publist_id":"3785","oa_version":"Preprint","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1202.4140"}],"scopus_import":"1","department":[{"_id":"KrCh"}],"volume":7561,"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"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"}],"citation":{"ista":"Chatterjee K, Chmelik M, Majumdar R. 2012. Equivalence of games with probabilistic uncertainty and partial observation games. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 7561, 385–399.","apa":"Chatterjee, K., Chmelik, M., &#38; Majumdar, R. (2012). Equivalence of games with probabilistic uncertainty and partial observation games (Vol. 7561, pp. 385–399). Presented at the ATVA: Automated Technology for Verification and Analysis, Thiruvananthapuram, India: Springer. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_30\">https://doi.org/10.1007/978-3-642-33386-6_30</a>","ama":"Chatterjee K, Chmelik M, Majumdar R. Equivalence of games with probabilistic uncertainty and partial observation games. In: Vol 7561. Springer; 2012:385-399. doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_30\">10.1007/978-3-642-33386-6_30</a>","mla":"Chatterjee, Krishnendu, et al. <i>Equivalence of Games with Probabilistic Uncertainty and Partial Observation Games</i>. Vol. 7561, Springer, 2012, pp. 385–99, doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_30\">10.1007/978-3-642-33386-6_30</a>.","ieee":"K. Chatterjee, M. Chmelik, and R. Majumdar, “Equivalence of games with probabilistic uncertainty and partial observation games,” presented at the ATVA: Automated Technology for Verification and Analysis, Thiruvananthapuram, India, 2012, vol. 7561, pp. 385–399.","short":"K. Chatterjee, M. Chmelik, R. Majumdar, in:, Springer, 2012, pp. 385–399.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Ritankar Majumdar. “Equivalence of Games with Probabilistic Uncertainty and Partial Observation Games,” 7561:385–99. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_30\">https://doi.org/10.1007/978-3-642-33386-6_30</a>."},"doi":"10.1007/978-3-642-33386-6_30"},{"doi":"10.1109/LICS.2012.30","citation":{"ama":"Chatterjee K, Velner Y. Mean payoff pushdown games. In: <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2012. doi:<a href=\"https://doi.org/10.1109/LICS.2012.30\">10.1109/LICS.2012.30</a>","ista":"Chatterjee K, Velner Y. 2012. Mean payoff pushdown games. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280438.","apa":"Chatterjee, K., &#38; Velner, Y. (2012). Mean payoff pushdown games. In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Dubrovnik, Croatia : IEEE. <a href=\"https://doi.org/10.1109/LICS.2012.30\">https://doi.org/10.1109/LICS.2012.30</a>","ieee":"K. Chatterjee and Y. Velner, “Mean payoff pushdown games,” in <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Dubrovnik, Croatia , 2012.","mla":"Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.” <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 6280438, IEEE, 2012, doi:<a href=\"https://doi.org/10.1109/LICS.2012.30\">10.1109/LICS.2012.30</a>.","short":"K. Chatterjee, Y. Velner, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","chicago":"Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.” In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE, 2012. <a href=\"https://doi.org/10.1109/LICS.2012.30\">https://doi.org/10.1109/LICS.2012.30</a>."},"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"scopus_import":"1","department":[{"_id":"KrCh"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1201.2829","open_access":"1"}],"quality_controlled":"1","oa_version":"Preprint","publist_id":"3770","_id":"2956","external_id":{"arxiv":["1201.2829"],"isi":["000309059900025"]},"conference":{"start_date":"2012-06-25","name":"LICS: Logic in Computer Science","location":"Dubrovnik, Croatia ","end_date":"2012-06-28"},"OA_place":"repository","arxiv":1,"related_material":{"record":[{"relation":"earlier_version","id":"5377","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), Microsoft faculty fellows award, the Israeli Centers of Research Excellence (ICORE) program, (Center No. 4/11), the RICH Model Toolkit (ICT COST Action IC0901), and was carried out in partial fulfillment of the requirements for the Ph.D. degree of the second author.\r\nA Technical Report of this paper is available via internal link.","day":"23","date_updated":"2025-09-30T08:08:13Z","title":"Mean payoff pushdown games","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Velner","first_name":"Yaron","full_name":"Velner, Yaron"}],"language":[{"iso":"eng"}],"OA_type":"green","publisher":"IEEE","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 solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and parity objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean payoff objectives. 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, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two-player pushdown games. Finally we also show that all the problems have the same computational complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.","lang":"eng"}],"date_created":"2018-12-11T12:00:32Z","month":"08","publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","status":"public","oa":1,"isi":1,"ec_funded":1,"type":"conference","article_number":"6280438","date_published":"2012-08-23T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","year":"2012","publication_status":"published"},{"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"citation":{"short":"K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.","chicago":"Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE, 2012. <a href=\"https://doi.org/10.1109/LICS.2012.29\">https://doi.org/10.1109/LICS.2012.29</a>.","ista":"Chatterjee K, Tracol M. 2012. Decidable problems for probabilistic automata on infinite words. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6280437.","ama":"Chatterjee K, Tracol M. Decidable problems for probabilistic automata on infinite words. In: <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2012. doi:<a href=\"https://doi.org/10.1109/LICS.2012.29\">10.1109/LICS.2012.29</a>","apa":"Chatterjee, K., &#38; Tracol, M. (2012). Decidable problems for probabilistic automata on infinite words. In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Dubrovnik, Croatia : IEEE. <a href=\"https://doi.org/10.1109/LICS.2012.29\">https://doi.org/10.1109/LICS.2012.29</a>","mla":"Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 6280437, IEEE, 2012, doi:<a href=\"https://doi.org/10.1109/LICS.2012.29\">10.1109/LICS.2012.29</a>.","ieee":"K. Chatterjee and M. Tracol, “Decidable problems for probabilistic automata on infinite words,” in <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Dubrovnik, Croatia , 2012."},"doi":"10.1109/LICS.2012.29","department":[{"_id":"KrCh"}],"scopus_import":"1","publist_id":"3769","_id":"2957","main_file_link":[{"url":"https://arxiv.org/abs/1107.2091","open_access":"1"}],"quality_controlled":"1","oa_version":"Preprint","conference":{"end_date":"2012-06-28","location":"Dubrovnik, Croatia ","name":"LICS: Logic in Computer Science","start_date":"2012-06-25"},"external_id":{"arxiv":["1107.2091"],"isi":["000309059900024"]},"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5384"}]},"day":"23","arxiv":1,"date_updated":"2025-09-30T08:07:39Z","title":"Decidable problems for probabilistic automata on infinite words","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"first_name":"Mathieu","last_name":"Tracol","full_name":"Tracol, Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87"}],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether words are accepted with probability arbitrarily close to 1. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound."}],"date_created":"2018-12-11T12:00:33Z","publisher":"IEEE","publication":"Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science","status":"public","corr_author":"1","month":"08","isi":1,"type":"conference","ec_funded":1,"oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_number":"6280437","date_published":"2012-08-23T00:00:00Z","article_processing_charge":"No","year":"2012","publication_status":"published"},{"publisher":"Elsevier","abstract":[{"text":"Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objectives. Our main results are as follows: (a) exponential memory is sufficient and may be necessary for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is logspace-equivalent to the problem of deciding the winner in mean-payoff parity games, which can thus be solved in NP ∩ coNP. As a consequence we also obtain a conceptually simple algorithm to solve mean-payoff parity games.","lang":"eng"}],"date_created":"2018-12-11T12:00:37Z","has_accepted_license":"1","intvolume":"       458","language":[{"iso":"eng"}],"publication":"Theoretical Computer Science","ddc":["004"],"month":"11","status":"public","page":"49 - 60","oa":1,"isi":1,"type":"journal_article","ec_funded":1,"file":[{"file_id":"5935","date_updated":"2020-07-14T12:45:57Z","checksum":"719e4a5af5a01ad3f2f7f7f05b3c2b09","file_name":"2012_Elsevier_Chatterjee.pdf","creator":"kschuh","date_created":"2019-02-06T11:56:22Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":351271}],"publication_status":"published","year":"2012","article_processing_charge":"No","date_published":"2012-11-02T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":458,"department":[{"_id":"KrCh"}],"scopus_import":"1","citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” <i>Theoretical Computer Science</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.tcs.2012.07.038\">https://doi.org/10.1016/j.tcs.2012.07.038</a>.","short":"K. Chatterjee, L. Doyen, Theoretical Computer Science 458 (2012) 49–60.","ieee":"K. Chatterjee and L. Doyen, “Energy parity games,” <i>Theoretical Computer Science</i>, vol. 458. Elsevier, pp. 49–60, 2012.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” <i>Theoretical Computer Science</i>, vol. 458, Elsevier, 2012, pp. 49–60, doi:<a href=\"https://doi.org/10.1016/j.tcs.2012.07.038\">10.1016/j.tcs.2012.07.038</a>.","ama":"Chatterjee K, Doyen L. Energy parity games. <i>Theoretical Computer Science</i>. 2012;458:49-60. doi:<a href=\"https://doi.org/10.1016/j.tcs.2012.07.038\">10.1016/j.tcs.2012.07.038</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2012). Energy parity games. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2012.07.038\">https://doi.org/10.1016/j.tcs.2012.07.038</a>","ista":"Chatterjee K, Doyen L. 2012. Energy parity games. Theoretical Computer Science. 458, 49–60."},"tmp":{"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)","short":"CC BY-NC-ND (4.0)"},"doi":"10.1016/j.tcs.2012.07.038","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"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"}],"pubrep_id":"935","oa_version":"Published Version","quality_controlled":"1","_id":"2972","publist_id":"3736","arxiv":1,"day":"02","related_material":{"record":[{"status":"public","id":"3851","relation":"earlier_version"}]},"file_date_updated":"2020-07-14T12:45:57Z","external_id":{"isi":["000310184900003"],"arxiv":["1001.5183"]},"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"title":"Energy parity games","date_updated":"2025-09-30T08:02:20Z"},{"project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"citation":{"chicago":"Kruckman, Alex, Sasha Rubin, John Sheridan, and Ben Zax. “A Myhill Nerode Theorem for Automata with Advice.” In <i>Proceedings GandALF 2012</i>, 96:238–46. Open Publishing Association, 2012. <a href=\"https://doi.org/10.4204/EPTCS.96.18\">https://doi.org/10.4204/EPTCS.96.18</a>.","short":"A. Kruckman, S. Rubin, J. Sheridan, B. Zax, in:, Proceedings GandALF 2012, Open Publishing Association, 2012, pp. 238–246.","ieee":"A. Kruckman, S. Rubin, J. Sheridan, and B. Zax, “A Myhill Nerode theorem for automata with advice,” in <i>Proceedings GandALF 2012</i>, Napoli, Italy, 2012, vol. 96, pp. 238–246.","mla":"Kruckman, Alex, et al. “A Myhill Nerode Theorem for Automata with Advice.” <i>Proceedings GandALF 2012</i>, vol. 96, Open Publishing Association, 2012, pp. 238–46, doi:<a href=\"https://doi.org/10.4204/EPTCS.96.18\">10.4204/EPTCS.96.18</a>.","apa":"Kruckman, A., Rubin, S., Sheridan, J., &#38; Zax, B. (2012). A Myhill Nerode theorem for automata with advice. In <i>Proceedings GandALF 2012</i> (Vol. 96, pp. 238–246). Napoli, Italy: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.96.18\">https://doi.org/10.4204/EPTCS.96.18</a>","ista":"Kruckman A, Rubin S, Sheridan J, Zax B. 2012. A Myhill Nerode theorem for automata with advice. Proceedings GandALF 2012. GandALF: Games, Automata, Logics and Formal Verification, EPTCS, vol. 96, 238–246.","ama":"Kruckman A, Rubin S, Sheridan J, Zax B. A Myhill Nerode theorem for automata with advice. In: <i>Proceedings GandALF 2012</i>. Vol 96. Open Publishing Association; 2012:238-246. doi:<a href=\"https://doi.org/10.4204/EPTCS.96.18\">10.4204/EPTCS.96.18</a>"},"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"},"doi":"10.4204/EPTCS.96.18","department":[{"_id":"KrCh"}],"scopus_import":1,"volume":96,"publist_id":"7325","_id":"495","oa_version":"Published Version","quality_controlled":"1","pubrep_id":"944","conference":{"location":"Napoli, Italy","name":"GandALF: Games, Automata, Logics and Formal Verification","start_date":"2012-09-06","end_date":"2012-09-08"},"file_date_updated":"2020-07-14T12:46:35Z","day":"07","date_updated":"2024-10-09T20:55:00Z","title":"A Myhill Nerode theorem for automata with advice","author":[{"first_name":"Alex","last_name":"Kruckman","full_name":"Kruckman, Alex"},{"first_name":"Sasha","last_name":"Rubin","full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87"},{"first_name":"John","last_name":"Sheridan","full_name":"Sheridan, John"},{"last_name":"Zax","first_name":"Ben","full_name":"Zax, Ben"}],"language":[{"iso":"eng"}],"intvolume":"        96","alternative_title":["EPTCS"],"date_created":"2018-12-11T11:46:47Z","abstract":[{"lang":"eng","text":"An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice."}],"has_accepted_license":"1","publisher":"Open Publishing Association","status":"public","publication":"Proceedings GandALF 2012","ddc":["004"],"month":"10","corr_author":"1","type":"conference","ec_funded":1,"oa":1,"page":"238 - 246","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_published":"2012-10-07T00:00:00Z","year":"2012","publication_status":"published","file":[{"file_id":"5152","date_updated":"2020-07-14T12:46:35Z","file_name":"IST-2018-944-v1+1_2012_Rubin_A_Myhill.pdf","creator":"system","checksum":"56277f95edc9d531fa3bdc5f9579fda8","relation":"main_file","date_created":"2018-12-12T10:15:31Z","content_type":"application/pdf","access_level":"open_access","file_size":97736}]},{"main_file_link":[{"open_access":"1","url":"https://arise.or.at/pubpdf/Interpretations_in_Trees_with_Countably_Many_Branches.pdf"}],"oa_version":"Preprint","quality_controlled":"1","publist_id":"7324","_id":"496","scopus_import":"1","department":[{"_id":"KrCh"}],"doi":"10.1109/LICS.2012.65","citation":{"ieee":"A. Rabinovich and S. Rubin, “Interpretations in trees with countably many branches,” presented at the LICS: Logic in Computer Science, Dubrovnik, Croatia, 2012.","mla":"Rabinovich, Alexander, and Sasha Rubin. <i>Interpretations in Trees with Countably Many Branches</i>. 6280474, IEEE, 2012, doi:<a href=\"https://doi.org/10.1109/LICS.2012.65\">10.1109/LICS.2012.65</a>.","apa":"Rabinovich, A., &#38; Rubin, S. (2012). Interpretations in trees with countably many branches. Presented at the LICS: Logic in Computer Science, Dubrovnik, Croatia: IEEE. <a href=\"https://doi.org/10.1109/LICS.2012.65\">https://doi.org/10.1109/LICS.2012.65</a>","ista":"Rabinovich A, Rubin S. 2012. Interpretations in trees with countably many branches. LICS: Logic in Computer Science, LICS, , 6280474.","ama":"Rabinovich A, Rubin S. Interpretations in trees with countably many branches. In: IEEE; 2012. doi:<a href=\"https://doi.org/10.1109/LICS.2012.65\">10.1109/LICS.2012.65</a>","chicago":"Rabinovich, Alexander, and Sasha Rubin. “Interpretations in Trees with Countably Many Branches.” IEEE, 2012. <a href=\"https://doi.org/10.1109/LICS.2012.65\">https://doi.org/10.1109/LICS.2012.65</a>.","short":"A. Rabinovich, S. Rubin, in:, IEEE, 2012."},"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"author":[{"full_name":"Rabinovich, Alexander","first_name":"Alexander","last_name":"Rabinovich"},{"first_name":"Sasha","last_name":"Rubin","full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2025-09-30T08:34:47Z","title":"Interpretations in trees with countably many branches","day":"01","external_id":{"isi":["000309059900061"]},"conference":{"name":"LICS: Logic in Computer Science","location":"Dubrovnik, Croatia","start_date":"2012-06-25","end_date":"2012-06-28"},"month":"01","status":"public","publisher":"IEEE","alternative_title":["LICS"],"date_created":"2018-12-11T11:46:47Z","abstract":[{"lang":"eng","text":"We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations."}],"language":[{"iso":"eng"}],"article_processing_charge":"No","year":"2012","publication_status":"published","article_number":"6280474","date_published":"2012-01-01T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"ec_funded":1,"type":"conference","isi":1},{"file":[{"file_id":"4712","date_updated":"2020-07-14T12:46:35Z","creator":"system","checksum":"f1b0dd99240800db2d7dbf9b5131fe5e","file_name":"IST-2018-943-v1+1_2012_Chatterjee_Faster_Algorithms.pdf","relation":"main_file","date_created":"2018-12-12T10:08:50Z","content_type":"application/pdf","access_level":"open_access","file_size":471236}],"publication_status":"published","year":"2012","date_published":"2012-09-01T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","page":"167 - 182","oa":1,"ec_funded":1,"type":"conference","month":"09","status":"public","ddc":["004"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","has_accepted_license":"1","abstract":[{"text":"One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.","lang":"eng"}],"date_created":"2018-12-11T11:46:48Z","alternative_title":["LIPIcs"],"intvolume":"        16","language":[{"iso":"eng"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Siddhesh","last_name":"Chaubal","full_name":"Chaubal, Siddhesh"},{"full_name":"Kamath, Pritish","first_name":"Pritish","last_name":"Kamath"}],"title":"Faster algorithms for alternating refinement relations","date_updated":"2025-01-14T12:24:50Z","day":"01","related_material":{"record":[{"status":"public","id":"5378","relation":"earlier_version"}]},"file_date_updated":"2020-07-14T12:46:35Z","conference":{"start_date":"2012-09-03","location":"Fontainebleau, France","name":"EACSL: European Association for Computer Science Logic","end_date":"2012-09-06"},"pubrep_id":"943","oa_version":"Published Version","quality_controlled":"1","_id":"497","publist_id":"7323","volume":16,"department":[{"_id":"KrCh"}],"scopus_import":1,"tmp":{"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)","short":"CC BY-NC-ND (4.0)"},"citation":{"short":"K. Chatterjee, S. Chaubal, P. Kamath, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–182.","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. “Faster Algorithms for Alternating Refinement Relations,” 16:167–82. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">https://doi.org/10.4230/LIPIcs.CSL.2012.167</a>.","ista":"Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating refinement relations. EACSL: European Association for Computer Science Logic, LIPIcs, vol. 16, 167–182.","ama":"Chatterjee K, Chaubal S, Kamath P. Faster algorithms for alternating refinement relations. In: Vol 16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:167-182. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">10.4230/LIPIcs.CSL.2012.167</a>","apa":"Chatterjee, K., Chaubal, S., &#38; Kamath, P. (2012). Faster algorithms for alternating refinement relations (Vol. 16, pp. 167–182). Presented at the EACSL: European Association for Computer Science Logic, Fontainebleau, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">https://doi.org/10.4230/LIPIcs.CSL.2012.167</a>","ieee":"K. Chatterjee, S. Chaubal, and P. Kamath, “Faster algorithms for alternating refinement relations,” presented at the EACSL: European Association for Computer Science Logic, Fontainebleau, France, 2012, vol. 16, pp. 167–182.","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Alternating Refinement Relations</i>. Vol. 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–82, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">10.4230/LIPIcs.CSL.2012.167</a>."},"doi":"10.4230/LIPIcs.CSL.2012.167","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}]},{"page":"33","oa":1,"type":"technical_report","file":[{"file_id":"5522","date_updated":"2020-07-14T12:46:38Z","relation":"main_file","date_created":"2018-12-12T11:54:00Z","creator":"system","checksum":"a03c08c1589dbb0c96183a8bcf3ab240","file_name":"IST-2012-002_IST-2012-0002.pdf","file_size":592098,"content_type":"application/pdf","access_level":"open_access"}],"publication_status":"published","year":"2012","article_processing_charge":"No","date_published":"2012-07-02T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","abstract":[{"lang":"eng","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 solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. 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, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded."}],"date_created":"2018-12-12T11:38:59Z","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"ddc":["000","005"],"corr_author":"1","month":"07","status":"public","day":"02","publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:38Z","related_material":{"record":[{"relation":"later_version","id":"2956","status":"public"}]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Yaron","last_name":"Velner","full_name":"Velner, Yaron"}],"title":"Mean-payoff pushdown games","date_updated":"2025-09-30T08:08:12Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2012-0002","citation":{"short":"K. Chatterjee, Y. Velner, Mean-Payoff Pushdown Games, IST Austria, 2012.","chicago":"Chatterjee, Krishnendu, and Yaron Velner. <i>Mean-Payoff Pushdown Games</i>. IST Austria, 2012. <a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">https://doi.org/10.15479/AT:IST-2012-0002</a>.","apa":"Chatterjee, K., &#38; Velner, Y. (2012). <i>Mean-payoff pushdown games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">https://doi.org/10.15479/AT:IST-2012-0002</a>","ama":"Chatterjee K, Velner Y. <i>Mean-Payoff Pushdown Games</i>. IST Austria; 2012. doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">10.15479/AT:IST-2012-0002</a>","ista":"Chatterjee K, Velner Y. 2012. Mean-payoff pushdown games, IST Austria, 33p.","mla":"Chatterjee, Krishnendu, and Yaron Velner. <i>Mean-Payoff Pushdown Games</i>. IST Austria, 2012, doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">10.15479/AT:IST-2012-0002</a>.","ieee":"K. Chatterjee and Y. Velner, <i>Mean-payoff pushdown games</i>. IST Austria, 2012."},"pubrep_id":"10","oa_version":"Published Version","_id":"5377"},{"type":"technical_report","oa":1,"page":"21","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2012-07-04T00:00:00Z","year":"2012","article_processing_charge":"No","publication_status":"published","file":[{"file_id":"5489","date_updated":"2020-07-14T12:46:39Z","relation":"main_file","date_created":"2018-12-12T11:53:28Z","file_name":"IST-2012-0001_IST-2012-0001.pdf","creator":"system","checksum":"ec8d1857cc7095d3de5107a0162ced37","file_size":394256,"content_type":"application/pdf","access_level":"open_access"}],"language":[{"iso":"eng"}],"alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.","lang":"eng"}],"has_accepted_license":"1","date_created":"2018-12-12T11:38:59Z","publisher":"IST Austria","ddc":["000","005"],"status":"public","corr_author":"1","month":"07","file_date_updated":"2020-07-14T12:46:39Z","related_material":{"record":[{"relation":"later_version","id":"497","status":"public"}]},"publication_identifier":{"issn":["2664-1690"]},"day":"04","date_updated":"2025-04-15T08:12:24Z","title":"Faster algorithms for alternating refinement relations","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chaubal, Siddhesh","first_name":"Siddhesh","last_name":"Chaubal"},{"first_name":"Pritish","last_name":"Kamath","full_name":"Kamath, Pritish"}],"doi":"10.15479/AT:IST-2012-0001","citation":{"apa":"Chatterjee, K., Chaubal, S., &#38; Kamath, P. (2012). <i>Faster algorithms for alternating refinement relations</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">https://doi.org/10.15479/AT:IST-2012-0001</a>","ista":"Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating refinement relations, IST Austria, 21p.","ama":"Chatterjee K, Chaubal S, Kamath P. <i>Faster Algorithms for Alternating Refinement Relations</i>. IST Austria; 2012. doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">10.15479/AT:IST-2012-0001</a>","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Alternating Refinement Relations</i>. IST Austria, 2012, doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">10.15479/AT:IST-2012-0001</a>.","ieee":"K. Chatterjee, S. Chaubal, and P. Kamath, <i>Faster algorithms for alternating refinement relations</i>. IST Austria, 2012.","short":"K. Chatterjee, S. Chaubal, P. Kamath, Faster Algorithms for Alternating Refinement Relations, IST Austria, 2012.","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. <i>Faster Algorithms for Alternating Refinement Relations</i>. IST Austria, 2012. <a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">https://doi.org/10.15479/AT:IST-2012-0001</a>."},"department":[{"_id":"KrCh"}],"_id":"5378","oa_version":"Published Version","pubrep_id":"14"},{"status":"public","publication":"Formal Methods in System Design","corr_author":"1","month":"10","ddc":["005"],"issue":"2","intvolume":"        43","language":[{"iso":"eng"}],"publisher":"Springer","date_created":"2018-12-11T12:01:33Z","abstract":[{"text":"We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational). ","lang":"eng"}],"has_accepted_license":"1","date_published":"2012-10-01T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file":[{"content_type":"application/pdf","access_level":"open_access","file_size":163983,"file_name":"IST-2014-303-v1+1_Survey_Partial-Observation_Stochastic_Parity_Games.pdf","creator":"system","checksum":"dd3d590f383bb2ac6cfda1489ac1c42a","relation":"main_file","date_created":"2018-12-12T10:11:27Z","date_updated":"2020-07-14T12:46:00Z","file_id":"4882"}],"article_processing_charge":"No","year":"2012","publication_status":"published","oa":1,"type":"journal_article","isi":1,"ec_funded":1,"page":"268 - 284","oa_version":"Submitted Version","quality_controlled":"1","publist_id":"3570","_id":"3128","pubrep_id":"303","doi":"10.1007/s10703-012-0164-2","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “A Survey of Partial-Observation Stochastic Parity Games.” <i>Formal Methods in System Design</i>. Springer, 2012. <a href=\"https://doi.org/10.1007/s10703-012-0164-2\">https://doi.org/10.1007/s10703-012-0164-2</a>.","short":"K. Chatterjee, L. Doyen, T.A. Henzinger, Formal Methods in System Design 43 (2012) 268–284.","mla":"Chatterjee, Krishnendu, et al. “A Survey of Partial-Observation Stochastic Parity Games.” <i>Formal Methods in System Design</i>, vol. 43, no. 2, Springer, 2012, pp. 268–84, doi:<a href=\"https://doi.org/10.1007/s10703-012-0164-2\">10.1007/s10703-012-0164-2</a>.","ieee":"K. Chatterjee, L. Doyen, and T. A. Henzinger, “A survey of partial-observation stochastic parity games,” <i>Formal Methods in System Design</i>, vol. 43, no. 2. Springer, pp. 268–284, 2012.","ama":"Chatterjee K, Doyen L, Henzinger TA. A survey of partial-observation stochastic parity games. <i>Formal Methods in System Design</i>. 2012;43(2):268-284. doi:<a href=\"https://doi.org/10.1007/s10703-012-0164-2\">10.1007/s10703-012-0164-2</a>","apa":"Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2012). A survey of partial-observation stochastic parity games. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-012-0164-2\">https://doi.org/10.1007/s10703-012-0164-2</a>","ista":"Chatterjee K, Doyen L, Henzinger TA. 2012. A survey of partial-observation stochastic parity games. Formal Methods in System Design. 43(2), 268–284."},"project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"name":"Quantitative Reactive Modeling","grant_number":"267989","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"volume":43,"scopus_import":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_updated":"2025-09-30T07:57:51Z","title":"A survey of partial-observation stochastic parity games","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"}],"external_id":{"isi":["000324114600006"]},"acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF NFN Grant No. S11407-N23(RiSE), ERC Start grant (279307: Graph Games), Microsoft faculty fellows award, ERC Advanced grant QUAREM, and FWF Grant No. S11403-N23 (RiSE).","file_date_updated":"2020-07-14T12:46:00Z","day":"01"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2012-07-01T00:00:00Z","year":"2012","article_processing_charge":"No","publication_status":"published","ec_funded":1,"type":"conference","oa":1,"page":"23 - 38","status":"public","month":"07","language":[{"iso":"eng"}],"intvolume":"      7358","alternative_title":["LNCS"],"abstract":[{"text":"We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates. ","lang":"eng"}],"date_created":"2018-12-11T12:01:35Z","publisher":"Springer","date_updated":"2025-06-11T08:10:20Z","title":"Efficient controller synthesis for consumption games with multiple resource types","author":[{"full_name":"Brázdil, Brázdil","first_name":"Brázdil","last_name":"Brázdil"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Kučera","first_name":"Antonín","full_name":"Kučera, Antonín"},{"last_name":"Novotny","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","full_name":"Novotny, Petr"}],"conference":{"start_date":"2012-07-07","name":"CAV: Computer Aided Verification","location":"Berkeley, CA, USA","end_date":"2012-07-13"},"external_id":{"arxiv":["1202.0796"]},"acknowledgement":"Tomas Brazdil, Antonin Kucera, and Petr Novotny are supported by the Czech Science Foundation, grant No. P202/10/1469. Krishnendu Chatterjee is supported by the FWF (Austrian Science Fund) NFN Grant No S11407-N23 (RiSE) and ERC Start grant (279307: Graph Games).","day":"01","arxiv":1,"publist_id":"3562","_id":"3135","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1202.0796"}],"quality_controlled":"1","oa_version":"Preprint","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"citation":{"mla":"Brázdil, Brázdil, et al. <i>Efficient Controller Synthesis for Consumption Games with Multiple Resource Types</i>. Vol. 7358, Springer, 2012, pp. 23–38, doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">10.1007/978-3-642-31424-7_8</a>.","ieee":"B. Brázdil, K. Chatterjee, A. Kučera, and P. Novotný, “Efficient controller synthesis for consumption games with multiple resource types,” presented at the CAV: Computer Aided Verification, Berkeley, CA, USA, 2012, vol. 7358, pp. 23–38.","apa":"Brázdil, B., Chatterjee, K., Kučera, A., &#38; Novotný, P. (2012). Efficient controller synthesis for consumption games with multiple resource types (Vol. 7358, pp. 23–38). Presented at the CAV: Computer Aided Verification, Berkeley, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">https://doi.org/10.1007/978-3-642-31424-7_8</a>","ama":"Brázdil B, Chatterjee K, Kučera A, Novotný P. Efficient controller synthesis for consumption games with multiple resource types. In: Vol 7358. Springer; 2012:23-38. doi:<a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">10.1007/978-3-642-31424-7_8</a>","ista":"Brázdil B, Chatterjee K, Kučera A, Novotný P. 2012. Efficient controller synthesis for consumption games with multiple resource types. CAV: Computer Aided Verification, LNCS, vol. 7358, 23–38.","chicago":"Brázdil, Brázdil, Krishnendu Chatterjee, Antonín Kučera, and Petr Novotný. “Efficient Controller Synthesis for Consumption Games with Multiple Resource Types,” 7358:23–38. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-31424-7_8\">https://doi.org/10.1007/978-3-642-31424-7_8</a>.","short":"B. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, in:, Springer, 2012, pp. 23–38."},"doi":"10.1007/978-3-642-31424-7_8","department":[{"_id":"KrCh"}],"scopus_import":"1","volume":7358},{"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"}],"title":"An O(n2) time algorithm for alternating Büchi games","date_updated":"2025-09-29T11:45:12Z","day":"01","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, Vienna Science and Technology Fund (WWTF) Grant ICT10-002, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","related_material":{"record":[{"relation":"earlier_version","id":"5379","status":"public"},{"status":"public","id":"2141","relation":"later_version"}]},"arxiv":1,"OA_place":"repository","conference":{"end_date":"2012-01-19","location":"Kyoto, Japan","name":"SODA: Symposium on Discrete Algorithms","start_date":"2012-01-17"},"external_id":{"arxiv":["1109.5018"]},"pubrep_id":"15","_id":"3165","publist_id":"3519","oa_version":"Preprint","quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1109.5018","open_access":"1"}],"department":[{"_id":"KrCh"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"doi":"10.1137/1.9781611973099.109","citation":{"chicago":"Chatterjee, Krishnendu, and Monika Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1386–99. SIAM, 2012. <a href=\"https://doi.org/10.1137/1.9781611973099.109\">https://doi.org/10.1137/1.9781611973099.109</a>.","short":"K. Chatterjee, M. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.","mla":"Chatterjee, Krishnendu, and Monika Henzinger. “An O(N2) Time Algorithm for Alternating Büchi Games.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, SIAM, 2012, pp. 1386–99, doi:<a href=\"https://doi.org/10.1137/1.9781611973099.109\">10.1137/1.9781611973099.109</a>.","ieee":"K. Chatterjee and M. Henzinger, “An O(n2) time algorithm for alternating Büchi games,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Kyoto, Japan, 2012, pp. 1386–1399.","apa":"Chatterjee, K., &#38; Henzinger, M. (2012). An O(n2) time algorithm for alternating Büchi games. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1386–1399). Kyoto, Japan: SIAM. <a href=\"https://doi.org/10.1137/1.9781611973099.109\">https://doi.org/10.1137/1.9781611973099.109</a>","ama":"Chatterjee K, Henzinger M. An O(n2) time algorithm for alternating Büchi games. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. SIAM; 2012:1386-1399. doi:<a href=\"https://doi.org/10.1137/1.9781611973099.109\">10.1137/1.9781611973099.109</a>","ista":"Chatterjee K, Henzinger M. 2012. An O(n2) time algorithm for alternating Büchi games. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1386–1399."},"publication_status":"published","article_processing_charge":"No","year":"2012","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2012-01-01T00:00:00Z","page":"1386 - 1399","type":"conference","ec_funded":1,"oa":1,"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","corr_author":"1","status":"public","month":"01","abstract":[{"text":"Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m &gt; n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m &gt; n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.","lang":"eng"}],"date_created":"2018-12-11T12:01:46Z","publisher":"SIAM","OA_type":"green","language":[{"iso":"eng"}]},{"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_updated":"2025-06-11T08:06:25Z","title":"Synthesizing protocols for digital contract signing","arxiv":1,"acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 (Modern Graph Algorithmic Techniques in Formal Verification), FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nThe authors would like to thank Avik Chaudhuri for his invaluable help and feedback.","day":"20","external_id":{"arxiv":["1004.2697"]},"conference":{"start_date":"2012-01-22","location":"Philadelphia, PA, USA","name":"VMCAI: Verification, Model Checking and Abstract Interpretation","end_date":"2012-01-24"},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1004.2697"}],"quality_controlled":"1","oa_version":"Preprint","publist_id":"3405","_id":"3252","volume":7148,"department":[{"_id":"KrCh"}],"scopus_import":"1","citation":{"chicago":"Chatterjee, Krishnendu, and Vishwanath Raman. “Synthesizing Protocols for Digital Contract Signing,” 7148:152–68. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>.","short":"K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 152–168.","ieee":"K. Chatterjee and V. Raman, “Synthesizing protocols for digital contract signing,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA, 2012, vol. 7148, pp. 152–168.","mla":"Chatterjee, Krishnendu, and Vishwanath Raman. <i>Synthesizing Protocols for Digital Contract Signing</i>. Vol. 7148, Springer, 2012, pp. 152–68, doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>.","ista":"Chatterjee K, Raman V. 2012. Synthesizing protocols for digital contract signing. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS, vol. 7148, 152–168.","ama":"Chatterjee K, Raman V. Synthesizing protocols for digital contract signing. In: Vol 7148. Springer; 2012:152-168. doi:<a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">10.1007/978-3-642-27940-9_11</a>","apa":"Chatterjee, K., &#38; Raman, V. (2012). Synthesizing protocols for digital contract signing (Vol. 7148, pp. 152–168). Presented at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-27940-9_11\">https://doi.org/10.1007/978-3-642-27940-9_11</a>"},"doi":"10.1007/978-3-642-27940-9_11","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"article_processing_charge":"No","year":"2012","publication_status":"published","date_published":"2012-01-20T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"152 - 168","oa":1,"type":"conference","ec_funded":1,"month":"01","status":"public","publisher":"Springer","alternative_title":["LNCS"],"date_created":"2018-12-11T12:02:16Z","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, the trusted third party (TTP) and the protocols as path formulas in Linear Temporal Logic (LTL) and prove that the satisfaction of the objectives of the agents and the TTP imply satisfaction of the protocol objectives. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail in synthesizing these protocols, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee synthesis is attack-free; no subset of participants can violate the objectives of the other participants without violating their own objectives; (b) the Asokan-Shoup-Waidner (ASW) certified mail protocol that has known vulnerabilities is not a solution of AGS; and (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution of AGS. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can generate correct protocols and automatically discover vulnerabilities. The solution to assume-guarantee synthesis can be computed efficiently as the secure equilibrium solution of three-player graph games. © 2012 Springer-Verlag."}],"intvolume":"      7148","language":[{"iso":"eng"}]},{"title":"The complexity of stochastic Müller games","date_updated":"2025-09-30T07:45:01Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"isi":["000300468000002"]},"day":"01","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.","_id":"3254","publist_id":"3403","oa_version":"None","quality_controlled":"1","main_file_link":[{"url":"http://arise.or.at/pubpdf/The_complexity_of_stochastic_M___u_ller_games.pdf"}],"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"doi":"10.1016/j.ic.2011.11.004","citation":{"short":"K. Chatterjee, Information and Computation 211 (2012) 29–48.","chicago":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” <i>Information and Computation</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">https://doi.org/10.1016/j.ic.2011.11.004</a>.","ama":"Chatterjee K. The complexity of stochastic Müller games. <i>Information and Computation</i>. 2012;211:29-48. doi:<a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">10.1016/j.ic.2011.11.004</a>","apa":"Chatterjee, K. (2012). The complexity of stochastic Müller games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">https://doi.org/10.1016/j.ic.2011.11.004</a>","ista":"Chatterjee K. 2012. The complexity of stochastic Müller games. Information and Computation. 211, 29–48.","mla":"Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” <i>Information and Computation</i>, vol. 211, Elsevier, 2012, pp. 29–48, doi:<a href=\"https://doi.org/10.1016/j.ic.2011.11.004\">10.1016/j.ic.2011.11.004</a>.","ieee":"K. Chatterjee, “The complexity of stochastic Müller games,” <i>Information and Computation</i>, vol. 211. Elsevier, pp. 29–48, 2012."},"scopus_import":"1","department":[{"_id":"KrCh"}],"volume":211,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2012-02-01T00:00:00Z","publication_status":"published","year":"2012","article_processing_charge":"No","type":"journal_article","ec_funded":1,"isi":1,"page":"29 - 48","corr_author":"1","publication":"Information and Computation","status":"public","month":"02","language":[{"iso":"eng"}],"intvolume":"       211","date_created":"2018-12-11T12:02:17Z","abstract":[{"text":"The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also study the complexity of stochastic Müller games and show that both the qualitative and quantitative analysis problems are PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes.","lang":"eng"}],"publisher":"Elsevier"},{"date_published":"2012-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_id":"7863","date_updated":"2020-07-14T12:46:05Z","date_created":"2020-05-15T12:53:12Z","relation":"main_file","file_name":"2012_MEMICS_Chatterjee.pdf","creator":"dernst","checksum":"eed2cc1e76b160418c977e76e8899a60","file_size":114060,"access_level":"open_access","content_type":"application/pdf"}],"publication_status":"published","year":"2012","article_processing_charge":"No","oa":1,"type":"conference","page":"37 - 46","month":"01","status":"public","ddc":["000"],"intvolume":"      7119","language":[{"iso":"eng"}],"publisher":"Springer","date_created":"2018-12-11T12:02:17Z","has_accepted_license":"1","abstract":[{"lang":"eng","text":"In this paper we survey results of two-player games on graphs and Markov decision processes with parity, mean-payoff and energy objectives, and the combination of mean-payoff and energy objectives with parity objectives. These problems have applications in verification and synthesis of reactive systems in resource-constrained environments."}],"alternative_title":["LNCS"],"title":"Games and Markov decision processes with mean payoff parity and energy parity objectives","date_updated":"2021-01-12T07:42:10Z","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}],"conference":{"location":"Lednice, Czech Republic","name":"MEMICS: Mathematical and Engineering Methods in Computer Science","start_date":"2011-10-14","end_date":"2011-10-16"},"day":"01","acknowledgement":"This work was partially supported by FWF NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.","file_date_updated":"2020-07-14T12:46:05Z","quality_controlled":"1","oa_version":"Submitted Version","_id":"3255","publist_id":"3400","citation":{"ieee":"K. Chatterjee and L. Doyen, “Games and Markov decision processes with mean payoff parity and energy parity objectives,” presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic, 2012, vol. 7119, pp. 37–46.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives</i>. Vol. 7119, Springer, 2012, pp. 37–46, doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>.","ama":"Chatterjee K, Doyen L. Games and Markov decision processes with mean payoff parity and energy parity objectives. In: Vol 7119. Springer; 2012:37-46. doi:<a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">10.1007/978-3-642-25929-6_3</a>","ista":"Chatterjee K, Doyen L. 2012. Games and Markov decision processes with mean payoff parity and energy parity objectives. MEMICS: Mathematical and Engineering Methods in Computer Science, LNCS, vol. 7119, 37–46.","apa":"Chatterjee, K., &#38; Doyen, L. (2012). Games and Markov decision processes with mean payoff parity and energy parity objectives (Vol. 7119, pp. 37–46). Presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games and Markov Decision Processes with Mean Payoff Parity and Energy Parity Objectives,” 7119:37–46. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-25929-6_3\">https://doi.org/10.1007/978-3-642-25929-6_3</a>.","short":"K. Chatterjee, L. Doyen, in:, Springer, 2012, pp. 37–46."},"doi":"10.1007/978-3-642-25929-6_3","project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"}],"volume":7119,"department":[{"_id":"KrCh"}],"scopus_import":1}]