[{"doi":"10.1007/978-3-319-08867-9_31","_id":"2063","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"5412","relation":"earlier_version"},{"status":"public","id":"5413","relation":"earlier_version"},{"status":"public","relation":"earlier_version","id":"5414"},{"relation":"dissertation_contains","id":"1155","status":"public"}]},"intvolume":"      8559","ec_funded":1,"title":"CEGAR for qualitative analysis of probabilistic systems","citation":{"apa":"Chatterjee, K., Chmelik, M., &#38; Daca, P. (2014). CEGAR for qualitative analysis of probabilistic systems (Vol. 8559, pp. 473–490). Presented at the CAV: Computer Aided Verification, Vienna, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">https://doi.org/10.1007/978-3-319-08867-9_31</a>","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Przemyslaw Daca. “CEGAR for Qualitative Analysis of Probabilistic Systems,” 8559:473–90. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">https://doi.org/10.1007/978-3-319-08867-9_31</a>.","ista":"Chatterjee K, Chmelik M, Daca P. 2014. CEGAR for qualitative analysis of probabilistic systems. CAV: Computer Aided Verification, LNCS, vol. 8559, 473–490.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. Vol. 8559, Springer, 2014, pp. 473–90, doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">10.1007/978-3-319-08867-9_31</a>.","ieee":"K. Chatterjee, M. Chmelik, and P. Daca, “CEGAR for qualitative analysis of probabilistic systems,” presented at the CAV: Computer Aided Verification, Vienna, Austria, 2014, vol. 8559, pp. 473–490.","ama":"Chatterjee K, Chmelik M, Daca P. CEGAR for qualitative analysis of probabilistic systems. In: Vol 8559. Springer; 2014:473-490. doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">10.1007/978-3-319-08867-9_31</a>","short":"K. Chatterjee, M. Chmelik, P. Daca, in:, Springer, 2014, pp. 473–490."},"publist_id":"4978","date_created":"2018-12-11T11:55:30Z","year":"2014","date_updated":"2023-09-07T11:58:33Z","quality_controlled":"1","volume":8559,"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"page":"473 - 490","type":"conference","status":"public","date_published":"2014-07-01T00:00:00Z","alternative_title":["LNCS"],"publisher":"Springer","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"name":"Moderne Concurrency Paradigms","call_identifier":"FWF","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems.We focus on qualitative properties forMDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation ofMDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.We present an automated technique for assume-guarantee style reasoning for compositional analysis ofMDPs with qualitative properties by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements."}],"day":"01","oa_version":"None","month":"07","conference":{"start_date":"2014-07-18","name":"CAV: Computer Aided Verification","end_date":"2014-07-22","location":"Vienna, Austria"},"publication_status":"published","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin"},{"first_name":"Przemyslaw","full_name":"Daca, Przemyslaw","last_name":"Daca","id":"49351290-F248-11E8-B48F-1D18A9856A87"}]},{"scopus_import":"1","intvolume":"       547","title":"Approximating the minimum cycle mean","oa":1,"date_updated":"2022-09-09T11:50:58Z","issue":"C","article_processing_charge":"No","publication":"Theoretical Computer Science","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1307.4473"}],"day":"28","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"08","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Krinninger, Sebastian","first_name":"Sebastian","last_name":"Krinninger"},{"full_name":"Loitzenbauer, Veronika","first_name":"Veronika","last_name":"Loitzenbauer"},{"last_name":"Raskin","full_name":"Raskin, Michael","first_name":"Michael"}],"arxiv":1,"status":"public","type":"journal_article","ec_funded":1,"publist_id":"5836","date_created":"2018-12-11T11:51:40Z","citation":{"ama":"Chatterjee K, Henzinger MH, Krinninger S, Loitzenbauer V, Raskin M. Approximating the minimum cycle mean. <i>Theoretical Computer Science</i>. 2014;547(C):104-116. doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">10.1016/j.tcs.2014.06.031</a>","ieee":"K. Chatterjee, M. H. Henzinger, S. Krinninger, V. Loitzenbauer, and M. Raskin, “Approximating the minimum cycle mean,” <i>Theoretical Computer Science</i>, vol. 547, no. C. Elsevier, pp. 104–116, 2014.","short":"K. Chatterjee, M.H. Henzinger, S. Krinninger, V. Loitzenbauer, M. Raskin, Theoretical Computer Science 547 (2014) 104–116.","ista":"Chatterjee K, Henzinger MH, Krinninger S, Loitzenbauer V, Raskin M. 2014. Approximating the minimum cycle mean. Theoretical Computer Science. 547(C), 104–116.","mla":"Chatterjee, Krishnendu, et al. “Approximating the Minimum Cycle Mean.” <i>Theoretical Computer Science</i>, vol. 547, no. C, Elsevier, 2014, pp. 104–16, doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">10.1016/j.tcs.2014.06.031</a>.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, and Michael Raskin. “Approximating the Minimum Cycle Mean.” <i>Theoretical Computer Science</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">https://doi.org/10.1016/j.tcs.2014.06.031</a>.","apa":"Chatterjee, K., Henzinger, M. H., Krinninger, S., Loitzenbauer, V., &#38; Raskin, M. (2014). Approximating the minimum cycle mean. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2014.06.031\">https://doi.org/10.1016/j.tcs.2014.06.031</a>"},"year":"2014","doi":"10.1016/j.tcs.2014.06.031","article_type":"original","_id":"1375","external_id":{"arxiv":["1307.4473"]},"abstract":[{"text":"We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n×n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1+ε)-approximation algorithm for the problem and the running time of our algorithm is Õ(nωlog3(nW/ε)/ε),1 where O(nω) is the time required for the classic n×n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ε)) factor in space a cycle with approximately optimal weight can be computed within the same time bound.","lang":"eng"}],"publication_status":"published","page":"104 - 116","department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":547,"publisher":"Elsevier","date_published":"2014-08-28T00:00:00Z","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}]},{"department":[{"_id":"KrCh"}],"page":"31","type":"technical_report","date_published":"2014-01-29T00:00:00Z","status":"public","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"file":[{"checksum":"4d6cda4bebed970926403ad6ad8c745f","file_name":"IST-2014-153-v1+1_main.pdf","file_id":"5500","date_updated":"2020-07-14T12:46:47Z","date_created":"2018-12-12T11:53:39Z","creator":"system","relation":"main_file","file_size":423322,"content_type":"application/pdf","access_level":"open_access"}],"day":"29","oa_version":"Published Version","publication_identifier":{"issn":["2664-1690"]},"month":"01","ddc":["000"],"publication_status":"published","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Przemyslaw","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","last_name":"Daca"},{"first_name":"Martin","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik"}],"doi":"10.15479/AT:IST-2014-153-v1-1","_id":"5412","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:47Z","has_accepted_license":"1","related_material":{"record":[{"status":"public","relation":"later_version","id":"2063"},{"relation":"later_version","id":"5413","status":"public"},{"status":"public","id":"5414","relation":"later_version"}]},"date_created":"2018-12-12T11:39:11Z","title":"CEGAR for qualitative analysis of probabilistic systems","citation":{"ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 31p.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>"},"year":"2014","oa":1,"pubrep_id":"153","date_updated":"2023-02-23T12:25:18Z"},{"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","date_published":"2014-02-06T00:00:00Z","type":"technical_report","status":"public","department":[{"_id":"KrCh"}],"page":"33","ddc":["000"],"publication_identifier":{"issn":["2664-1690"]},"month":"02","oa_version":"Published Version","day":"06","file":[{"checksum":"ce4967a184d84863eec76c66cbac1614","file_name":"IST-2014-153-v2+2_main.pdf","file_id":"5539","date_created":"2018-12-12T11:54:17Z","date_updated":"2020-07-14T12:46:47Z","creator":"system","content_type":"application/pdf","file_size":606049,"access_level":"open_access","relation":"main_file"}],"abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Przemyslaw","full_name":"Daca, Przemyslaw","last_name":"Daca","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","first_name":"Martin"}],"publication_status":"published","doi":"10.15479/AT:IST-2014-153-v2-2","file_date_updated":"2020-07-14T12:46:47Z","language":[{"iso":"eng"}],"_id":"5413","related_material":{"record":[{"id":"2063","relation":"later_version","status":"public"},{"status":"public","id":"5412","relation":"earlier_version"},{"relation":"later_version","id":"5414","status":"public"}]},"has_accepted_license":"1","pubrep_id":"164","date_updated":"2023-02-23T12:25:18Z","oa":1,"year":"2014","date_created":"2018-12-12T11:39:11Z","title":"CEGAR for qualitative analysis of probabilistic systems","citation":{"apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014."}},{"year":"2014","oa":1,"date_updated":"2023-02-23T12:25:15Z","pubrep_id":"165","title":"CEGAR for qualitative analysis of probabilistic systems","date_created":"2018-12-12T11:39:12Z","citation":{"ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>"},"has_accepted_license":"1","related_material":{"record":[{"status":"public","id":"2063","relation":"later_version"},{"relation":"earlier_version","id":"5412","status":"public"},{"status":"public","relation":"earlier_version","id":"5413"}]},"_id":"5414","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:48Z","doi":"10.15479/AT:IST-2014-153-v3-1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Przemyslaw","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","last_name":"Daca"},{"full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"month":"02","ddc":["000"],"file":[{"content_type":"application/pdf","access_level":"open_access","file_size":606227,"relation":"main_file","creator":"system","date_updated":"2020-07-14T12:46:48Z","date_created":"2018-12-12T11:53:03Z","checksum":"87b93fe9af71fc5c94b0eb6151537e11","file_id":"5464","file_name":"IST-2014-153-v3+1_main.pdf"}],"abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"07","oa_version":"Published Version","date_published":"2014-02-07T00:00:00Z","status":"public","type":"technical_report","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","page":"33","department":[{"_id":"KrCh"}]},{"file_date_updated":"2020-07-14T12:46:48Z","language":[{"iso":"eng"}],"_id":"5415","doi":"10.15479/AT:IST-2014-170-v1-1","oa":1,"pubrep_id":"170","date_updated":"2023-02-23T12:26:19Z","year":"2014","date_created":"2018-12-12T11:39:12Z","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2014.","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2014.","ista":"Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria, 27p.","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2014). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>"},"title":"Nested weighted automata","has_accepted_license":"1","related_material":{"record":[{"status":"public","relation":"later_version","id":"1656"},{"id":"467","relation":"later_version","status":"public"},{"id":"5436","relation":"later_version","status":"public"}]},"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","date_published":"2014-02-19T00:00:00Z","type":"technical_report","status":"public","page":"27","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","first_name":"Jan","full_name":"Otop, Jan"}],"publication_status":"published","ddc":["004"],"publication_identifier":{"issn":["2664-1690"]},"month":"02","oa_version":"Published Version","day":"19","file":[{"content_type":"application/pdf","relation":"main_file","file_size":573457,"access_level":"open_access","creator":"system","date_created":"2018-12-12T11:53:36Z","date_updated":"2020-07-14T12:46:48Z","checksum":"31f90dcf2cf899c3f8c6427cfcc2b3c7","file_id":"5497","file_name":"IST-2014-170-v1+1_main.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Recently there has been a significant effort to add quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.  ","lang":"eng"}]},{"file":[{"date_updated":"2020-07-14T12:46:49Z","date_created":"2018-12-12T11:53:07Z","file_id":"5468","file_name":"IST-2014-176-v1+1_icalp_14.pdf","checksum":"1d6958aa60050e1c3e932c6e5f34c39f","access_level":"open_access","file_size":328253,"content_type":"application/pdf","relation":"main_file","creator":"system"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results."}],"day":"22","oa_version":"Published Version","publication_identifier":{"issn":["2664-1690"]},"month":"03","ddc":["000","005"],"publication_status":"published","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Laurent","full_name":"Doyen, Laurent","last_name":"Doyen"}],"page":"18","department":[{"_id":"KrCh"}],"type":"technical_report","status":"public","date_published":"2014-03-22T00:00:00Z","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","related_material":{"record":[{"id":"2163","relation":"later_version","status":"public"}]},"has_accepted_license":"1","date_created":"2018-12-12T11:39:13Z","citation":{"apa":"Chatterjee, K., &#38; Doyen, L. (2014). <i>Games with a weak adversary</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>.","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.","ama":"Chatterjee K, Doyen L. <i>Games with a Weak Adversary</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>","ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014.","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014."},"title":"Games with a weak adversary","year":"2014","pubrep_id":"176","date_updated":"2023-02-23T10:30:58Z","oa":1,"doi":"10.15479/AT:IST-2014-176-v1-1","_id":"5418","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:49Z"},{"has_accepted_license":"1","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.","mla":"Chatterjee, Krishnendu, et al. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>"},"title":"Improved algorithms for reachability and shortest path on low tree-width graphs","date_created":"2018-12-12T11:39:13Z","date_updated":"2021-01-12T08:02:03Z","oa":1,"pubrep_id":"187","year":"2014","doi":"10.15479/AT:IST-2014-187-v1-1","file_date_updated":"2020-07-14T12:46:50Z","_id":"5419","language":[{"iso":"eng"}],"oa_version":"Published Version","day":"14","abstract":[{"lang":"eng","text":"We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:\r\n1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).\r\n2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.\r\nOur algorithms improve all existing results, and use very simple data structures."}],"file":[{"checksum":"c608e66030a4bf51d2d99b451f539b99","file_name":"IST-2014-187-v1+1_main_full_tech.pdf","file_id":"5548","date_updated":"2020-07-14T12:46:50Z","date_created":"2018-12-12T11:54:25Z","creator":"system","file_size":670031,"access_level":"open_access","content_type":"application/pdf","relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"month":"04","publication_identifier":{"issn":["2664-1690"]},"publication_status":"published","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"}],"department":[{"_id":"KrCh"}],"page":"34","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","status":"public","type":"technical_report","date_published":"2014-04-14T00:00:00Z"},{"publication_status":"published","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen"}],"publication_identifier":{"issn":["2664-1690"]},"month":"04","ddc":["000","005"],"abstract":[{"text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_size":584368,"relation":"main_file","access_level":"open_access","content_type":"application/pdf","creator":"system","date_updated":"2020-07-14T12:46:50Z","date_created":"2018-12-12T11:53:58Z","checksum":"49e0fd3e62650346daf7dc04604f7a0a","file_name":"IST-2014-191-v1+1_main_full.pdf","file_id":"5520"}],"oa_version":"Published Version","day":"14","type":"technical_report","date_published":"2014-04-14T00:00:00Z","status":"public","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"department":[{"_id":"KrCh"}],"page":"49","year":"2014","oa":1,"date_updated":"2021-01-12T08:02:05Z","pubrep_id":"191","title":"The value 1 problem for concurrent mean-payoff games","date_created":"2018-12-12T11:39:14Z","citation":{"mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.","short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria, 2014.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>"},"has_accepted_license":"1","_id":"5420","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:50Z","doi":"10.15479/AT:IST-2014-191-v1-1"},{"has_accepted_license":"1","related_material":{"record":[{"status":"public","id":"5432","relation":"later_version"},{"relation":"later_version","id":"5440","status":"public"}]},"date_created":"2018-12-12T11:39:14Z","title":"The complexity of evolution on graphs","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2014). <i>The complexity of evolution on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolution on graphs</i>. IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolution on Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on Graphs, IST Austria, 2014."},"year":"2014","date_updated":"2023-02-23T12:26:33Z","pubrep_id":"190","oa":1,"doi":"10.15479/AT:IST-2014-190-v2-2","_id":"5421","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:50Z","file":[{"date_updated":"2020-07-14T12:46:50Z","date_created":"2018-12-12T11:54:16Z","file_id":"5538","checksum":"42f3d8b563286eb0d903832bd9a848d3","file_name":"IST-2014-190-v2+2_main_full.pdf","relation":"main_file","content_type":"application/pdf","file_size":443529,"access_level":"open_access","creator":"system"},{"checksum":"0c9a2fd822309719634495a35957e34d","file_id":"6852","file_name":"IST-2014-190-v1+1_main_full.pdf","date_created":"2019-09-06T07:30:20Z","date_updated":"2020-07-14T12:46:50Z","creator":"kschuh","file_size":440911,"content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time."}],"oa_version":"Published Version","day":"18","month":"04","publication_identifier":{"issn":["2664-1690"]},"ddc":["000","005"],"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"publication_status":"published","department":[{"_id":"KrCh"}],"page":"27","type":"technical_report","date_published":"2014-04-18T00:00:00Z","status":"public","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria"},{"type":"technical_report","date_published":"2014-07-29T00:00:00Z","status":"public","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"department":[{"_id":"KrCh"}],"page":"14","publication_status":"published","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"last_name":"Kössler","full_name":"Kössler, Alexander","first_name":"Alexander"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722"},{"full_name":"Schmid, Ulrich","first_name":"Ulrich","last_name":"Schmid"}],"publication_identifier":{"issn":["2664-1690"]},"month":"07","ddc":["005"],"abstract":[{"text":"We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. ","lang":"eng"}],"file":[{"relation":"main_file","file_size":1270021,"access_level":"open_access","content_type":"application/pdf","creator":"system","date_created":"2018-12-12T11:53:53Z","date_updated":"2020-07-14T12:46:50Z","checksum":"4b8fde4d9ef6653837f6803921d83032","file_name":"IST-2014-300-v1+1_main.pdf","file_id":"5514"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"29","oa_version":"Published Version","_id":"5423","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:50Z","doi":"10.15479/AT:IST-2014-300-v1-1","year":"2014","pubrep_id":"300","date_updated":"2023-02-23T10:11:15Z","oa":1,"citation":{"apa":"Chatterjee, K., Kössler, A., Pavlogiannis, A., &#38; Schmid, U. (2014). <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>","ama":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>","ieee":"K. Chatterjee, A. Kössler, A. Pavlogiannis, and U. Schmid, <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria, 2014.","short":"K. Chatterjee, A. Kössler, A. Pavlogiannis, U. Schmid, A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks, IST Austria, 2014.","ista":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. 2014. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks, IST Austria, 14p.","mla":"Chatterjee, Krishnendu, et al. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Alexander Kössler, Andreas Pavlogiannis, and Ulrich Schmid. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>."},"date_created":"2018-12-12T11:39:15Z","title":"A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks","has_accepted_license":"1","related_material":{"record":[{"status":"public","relation":"later_version","id":"1714"}]}},{"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik"},{"last_name":"Gupta","full_name":"Gupta, Raghav","first_name":"Raghav"},{"full_name":"Kanodia, Ayush","first_name":"Ayush","last_name":"Kanodia"}],"publication_status":"published","oa_version":"Published Version","day":"09","abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty."}],"file":[{"creator":"system","content_type":"application/pdf","access_level":"open_access","file_size":655774,"relation":"main_file","checksum":"35009d5fad01198341e6c1a3353481b7","file_name":"IST-2014-305-v1+1_main.pdf","file_id":"5512","date_created":"2018-12-12T11:53:51Z","date_updated":"2020-07-14T12:46:51Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["005"],"publication_identifier":{"issn":["2664-1690"]},"month":"09","page":"12","department":[{"_id":"KrCh"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"date_published":"2014-09-09T00:00:00Z","type":"technical_report","status":"public","citation":{"apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2014). <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">https://doi.org/10.15479/AT:IST-2014-305-v1-1</a>","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">10.15479/AT:IST-2014-305-v1-1</a>","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria, 2014.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">10.15479/AT:IST-2014-305-v1-1</a>.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 12p.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">https://doi.org/10.15479/AT:IST-2014-305-v1-1</a>."},"title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","date_created":"2018-12-12T11:39:15Z","date_updated":"2023-02-23T12:25:52Z","oa":1,"pubrep_id":"305","year":"2014","related_material":{"record":[{"status":"public","relation":"later_version","id":"1732"},{"id":"5426","relation":"later_version","status":"public"}]},"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:51Z","language":[{"iso":"eng"}],"_id":"5424","doi":"10.15479/AT:IST-2014-305-v1-1"},{"language":[{"iso":"eng"}],"_id":"5426","file_date_updated":"2020-07-14T12:46:51Z","doi":"10.15479/AT:IST-2014-305-v2-1","year":"2014","pubrep_id":"311","date_updated":"2023-02-23T12:25:47Z","oa":1,"date_created":"2018-12-12T11:39:16Z","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","citation":{"apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2014). <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria, 2014.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">10.15479/AT:IST-2014-305-v2-1</a>","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 10p.","mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">10.15479/AT:IST-2014-305-v2-1</a>.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>."},"related_material":{"record":[{"status":"public","relation":"later_version","id":"1732"},{"status":"public","relation":"earlier_version","id":"5424"}]},"has_accepted_license":"1","date_published":"2014-09-29T00:00:00Z","type":"technical_report","status":"public","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","department":[{"_id":"KrCh"}],"page":"10","publication_status":"published","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Gupta","first_name":"Raghav","full_name":"Gupta, Raghav"},{"full_name":"Kanodia, Ayush","first_name":"Ayush","last_name":"Kanodia"}],"month":"09","publication_identifier":{"issn":["2664-1690"]},"ddc":["005"],"abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty."}],"file":[{"date_created":"2018-12-12T11:54:15Z","date_updated":"2020-07-14T12:46:51Z","file_id":"5537","checksum":"730c0a8e97cf2712a884b2cc423f3919","file_name":"IST-2014-305-v2+1_main2.pdf","file_size":656019,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","creator":"system"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"29","oa_version":"Published Version"},{"publication_status":"published","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas"}],"publication_identifier":{"issn":["2664-1690"]},"month":"11","ddc":["000"],"file":[{"checksum":"9d3b90bf4fff74664f182f2d95ef727a","file_name":"IST-2014-314-v1+1_long.pdf","file_id":"5471","date_created":"2018-12-12T11:53:10Z","date_updated":"2020-07-14T12:46:52Z","creator":"system","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":405561}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.","lang":"eng"}],"oa_version":"Published Version","day":"05","date_published":"2014-11-05T00:00:00Z","type":"technical_report","status":"public","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","page":"24","department":[{"_id":"KrCh"}],"year":"2014","pubrep_id":"314","oa":1,"date_updated":"2021-01-12T08:02:09Z","date_created":"2018-12-12T11:39:16Z","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition balancing and reachability on low treewidth graphs, IST Austria, 24p.","mla":"Chatterjee, Krishnendu, et al. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">10.15479/AT:IST-2014-314-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">https://doi.org/10.15479/AT:IST-2014-314-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs, IST Austria, 2014.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Optimal tree-decomposition balancing and reachability on low treewidth graphs</i>. IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">10.15479/AT:IST-2014-314-v1-1</a>","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Optimal tree-decomposition balancing and reachability on low treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">https://doi.org/10.15479/AT:IST-2014-314-v1-1</a>"},"title":"Optimal tree-decomposition balancing and reachability on low treewidth graphs","has_accepted_license":"1","language":[{"iso":"eng"}],"_id":"5427","file_date_updated":"2020-07-14T12:46:52Z","doi":"10.15479/AT:IST-2014-314-v1-1"},{"doi":"10.15479/AT:IST-2014-315-v1-1","file_date_updated":"2020-07-14T12:46:52Z","language":[{"iso":"eng"}],"_id":"5428","related_material":{"record":[{"status":"public","relation":"later_version","id":"1066"}]},"has_accepted_license":"1","oa":1,"pubrep_id":"315","date_updated":"2023-09-20T12:07:48Z","year":"2014","title":"Quantitative fair simulation games","date_created":"2018-12-12T11:39:16Z","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Quantitative Fair Simulation Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">10.15479/AT:IST-2014-315-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Otop J, Velner Y. 2014. Quantitative fair simulation games, IST Austria, 26p.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Yaron Velner. <i>Quantitative Fair Simulation Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>.","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, <i>Quantitative fair simulation games</i>. IST Austria, 2014.","ama":"Chatterjee K, Henzinger TA, Otop J, Velner Y. <i>Quantitative Fair Simulation Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">10.15479/AT:IST-2014-315-v1-1</a>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Quantitative Fair Simulation Games, IST Austria, 2014.","apa":"Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Velner, Y. (2014). <i>Quantitative fair simulation games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>"},"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","type":"technical_report","date_published":"2014-12-05T00:00:00Z","status":"public","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"page":"26","ddc":["004"],"month":"12","publication_identifier":{"issn":["2664-1690"]},"day":"05","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms.\r\n\r\nIn this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata.","lang":"eng"}],"file":[{"file_id":"5521","checksum":"b1d573bc04365625ff9974880c0aa807","file_name":"IST-2014-315-v1+1_report.pdf","date_updated":"2020-07-14T12:46:52Z","date_created":"2018-12-12T11:53:59Z","creator":"system","access_level":"open_access","content_type":"application/pdf","file_size":531046,"relation":"main_file"}],"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","first_name":"Jan","full_name":"Otop, Jan"},{"last_name":"Velner","first_name":"Yaron","full_name":"Velner, Yaron"}],"publication_status":"published"},{"_id":"9739","doi":"10.1371/journal.pcbi.1003818.s001","date_created":"2021-07-28T08:13:57Z","citation":{"chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, Ben Adlam, and Martin Novak. “Detailed Proofs for ‘The Time Scale of Evolutionary Innovation.’” Public Library of Science, 2014. <a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">https://doi.org/10.1371/journal.pcbi.1003818.s001</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Detailed Proofs for “The Time Scale of Evolutionary Innovation.”</i> Public Library of Science, 2014, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">10.1371/journal.pcbi.1003818.s001</a>.","ista":"Chatterjee K, Pavlogiannis A, Adlam B, Novak M. 2014. Detailed proofs for “The time scale of evolutionary innovation”, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">10.1371/journal.pcbi.1003818.s001</a>.","short":"K. Chatterjee, A. Pavlogiannis, B. Adlam, M. Novak, (2014).","ama":"Chatterjee K, Pavlogiannis A, Adlam B, Novak M. Detailed proofs for “The time scale of evolutionary innovation.” 2014. doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">10.1371/journal.pcbi.1003818.s001</a>","ieee":"K. Chatterjee, A. Pavlogiannis, B. Adlam, and M. Novak, “Detailed proofs for ‘The time scale of evolutionary innovation.’” Public Library of Science, 2014.","apa":"Chatterjee, K., Pavlogiannis, A., Adlam, B., &#38; Novak, M. (2014). Detailed proofs for “The time scale of evolutionary innovation.” Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">https://doi.org/10.1371/journal.pcbi.1003818.s001</a>"},"title":"Detailed proofs for “The time scale of evolutionary innovation”","date_updated":"2023-02-23T10:25:37Z","year":"2014","article_processing_charge":"No","related_material":{"record":[{"status":"public","relation":"used_in_publication","id":"2039"}]},"department":[{"_id":"KrCh"}],"publisher":"Public Library of Science","status":"public","type":"research_data_reference","date_published":"2014-09-11T00:00:00Z","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Adlam","full_name":"Adlam, Ben","first_name":"Ben"},{"last_name":"Novak","full_name":"Novak, Martin","first_name":"Martin"}],"day":"11","oa_version":"Published Version","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","month":"09"},{"doi":"10.1007/978-3-642-54013-4_15","_id":"10884","ec_funded":1,"citation":{"chicago":"Aminof, Benjamin, Swen Jacobs, Ayrat Khalimov, and Sasha Rubin. “Parameterized Model Checking of Token-Passing Systems.” In <i>Verification, Model Checking, and Abstract Interpretation</i>, 8318:262–81. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">https://doi.org/10.1007/978-3-642-54013-4_15</a>.","mla":"Aminof, Benjamin, et al. “Parameterized Model Checking of Token-Passing Systems.” <i>Verification, Model Checking, and Abstract Interpretation</i>, vol. 8318, Springer Nature, 2014, pp. 262–81, doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">10.1007/978-3-642-54013-4_15</a>.","ista":"Aminof B, Jacobs S, Khalimov A, Rubin S. 2014. Parameterized model checking of token-passing systems. Verification, Model Checking, and Abstract Interpretation. VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318, 262–281.","short":"B. Aminof, S. Jacobs, A. Khalimov, S. Rubin, in:, Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 262–281.","ama":"Aminof B, Jacobs S, Khalimov A, Rubin S. Parameterized model checking of token-passing systems. In: <i>Verification, Model Checking, and Abstract Interpretation</i>. Vol 8318. Springer Nature; 2014:262-281. doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">10.1007/978-3-642-54013-4_15</a>","ieee":"B. Aminof, S. Jacobs, A. Khalimov, and S. Rubin, “Parameterized model checking of token-passing systems,” in <i>Verification, Model Checking, and Abstract Interpretation</i>, San Diego, CA, United States, 2014, vol. 8318, pp. 262–281.","apa":"Aminof, B., Jacobs, S., Khalimov, A., &#38; Rubin, S. (2014). Parameterized model checking of token-passing systems. In <i>Verification, Model Checking, and Abstract Interpretation</i> (Vol. 8318, pp. 262–281). San Diego, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_15\">https://doi.org/10.1007/978-3-642-54013-4_15</a>"},"date_created":"2022-03-18T13:01:22Z","acknowledgement":"This work was supported by the Austrian Science Fund through grant P23499-N23\r\nand through the RiSE network (S11403, S11405, S11406, S11407-N23); ERC Starting Grant (279307: Graph Games); Vienna Science and Technology Fund (WWTF)\r\ngrants PROSEED, ICT12-059, and VRG11-005.","year":"2014","page":"262-281","department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":8318,"publisher":"Springer Nature","date_published":"2014-01-30T00:00:00Z","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"}],"external_id":{"arxiv":["1311.4425"]},"abstract":[{"lang":"eng","text":"We revisit the parameterized model checking problem for token-passing systems and specifications in indexed CTL  ∗ \\X. Emerson and Namjoshi (1995, 2003) have shown that parameterized model checking of indexed CTL  ∗ \\X in uni-directional token rings can be reduced to checking rings up to some cutoff size. Clarke et al. (2004) have shown a similar result for general topologies and indexed LTL \\X, provided processes cannot choose the directions for sending or receiving the token.\r\nWe unify and substantially extend these results by systematically exploring fragments of indexed CTL  ∗ \\X with respect to general topologies. For each fragment we establish whether a cutoff exists, and for some concrete topologies, such as rings, cliques and stars, we infer small cutoffs. Finally, we show that the problem becomes undecidable, and thus no cutoffs exist, if processes are allowed to choose the directions in which they send or from which they receive the token."}],"publication_status":"published","publication":"Verification, Model Checking, and Abstract Interpretation","language":[{"iso":"eng"}],"intvolume":"      8318","scopus_import":"1","title":"Parameterized model checking of token-passing systems","oa":1,"date_updated":"2022-05-17T08:36:01Z","article_processing_charge":"No","alternative_title":["LNCS"],"type":"conference","status":"public","oa_version":"Preprint","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.1311.4425","open_access":"1"}],"day":"30","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2014-01-19","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","end_date":"2014-01-21","location":"San Diego, CA, United States"},"publication_identifier":{"issn":["0302-9743"],"eisbn":["9783642540134"],"eissn":["1611-3349"],"isbn":["9783642540127"]},"month":"01","author":[{"first_name":"Benjamin","full_name":"Aminof, Benjamin","id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","last_name":"Aminof"},{"last_name":"Jacobs","first_name":"Swen","full_name":"Jacobs, Swen"},{"first_name":"Ayrat","full_name":"Khalimov, Ayrat","last_name":"Khalimov"},{"full_name":"Rubin, Sasha","first_name":"Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","last_name":"Rubin"}],"arxiv":1},{"language":[{"iso":"eng"}],"publication":"VMCAI 2014: Verification, Model Checking, and Abstract Interpretation","title":"Doomsday equilibria for omega-regular games","date_updated":"2023-02-23T12:52:24Z","article_processing_charge":"No","intvolume":"      8318","scopus_import":"1","alternative_title":["LNCS"],"status":"public","type":"conference","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"},{"first_name":"Emmanuel","full_name":"Filiot, Emmanuel","last_name":"Filiot"},{"first_name":"Jean-François","full_name":"Raskin, Jean-François","last_name":"Raskin"}],"arxiv":1,"day":"30","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"San Diego, CA, United States","end_date":"2014-01-21","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","start_date":"2014-01-19"},"publication_identifier":{"issn":["0302-9743"],"isbn":["9783642540127"],"eisbn":["9783642540134"],"eissn":["1611-3349"]},"month":"01","_id":"10885","doi":"10.1007/978-3-642-54013-4_5","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, Emmanuel Filiot, and Jean-François Raskin. “Doomsday Equilibria for Omega-Regular Games.” In <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>, 8318:78–97. Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">https://doi.org/10.1007/978-3-642-54013-4_5</a>.","ista":"Chatterjee K, Doyen L, Filiot E, Raskin J-F. 2014. Doomsday equilibria for omega-regular games. VMCAI 2014: Verification, Model Checking, and Abstract Interpretation. VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318, 78–97.","mla":"Chatterjee, Krishnendu, et al. “Doomsday Equilibria for Omega-Regular Games.” <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>, vol. 8318, Springer Nature, 2014, pp. 78–97, doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">10.1007/978-3-642-54013-4_5</a>.","short":"K. Chatterjee, L. Doyen, E. Filiot, J.-F. Raskin, in:, VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 78–97.","ama":"Chatterjee K, Doyen L, Filiot E, Raskin J-F. Doomsday equilibria for omega-regular games. In: <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>. Vol 8318. Springer Nature; 2014:78-97. doi:<a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">10.1007/978-3-642-54013-4_5</a>","ieee":"K. Chatterjee, L. Doyen, E. Filiot, and J.-F. Raskin, “Doomsday equilibria for omega-regular games,” in <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i>, San Diego, CA, United States, 2014, vol. 8318, pp. 78–97.","apa":"Chatterjee, K., Doyen, L., Filiot, E., &#38; Raskin, J.-F. (2014). Doomsday equilibria for omega-regular games. In <i>VMCAI 2014: Verification, Model Checking, and Abstract Interpretation</i> (Vol. 8318, pp. 78–97). San Diego, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-54013-4_5\">https://doi.org/10.1007/978-3-642-54013-4_5</a>"},"date_created":"2022-03-18T13:03:15Z","acknowledgement":" Supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No\r\nS11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","year":"2014","ec_funded":1,"related_material":{"record":[{"status":"public","relation":"later_version","id":"681"}]},"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"}],"page":"78-97","quality_controlled":"1","volume":8318,"publisher":"Springer Nature","date_published":"2014-01-30T00:00:00Z","publication_status":"published","external_id":{"arxiv":["1311.3238"]},"abstract":[{"lang":"eng","text":"Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information games.\r\nIn this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile such that all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players objective, then the objective of every player is violated.\r\nWe present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω-regular objectives, both for imperfect-information games, and for perfect-information games.We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games."}]},{"month":"05","oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprints.cs.univie.ac.at/3933/"}],"day":"01","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H"}],"type":"journal_article","status":"public","scopus_import":"1","intvolume":"        61","oa":1,"date_updated":"2025-06-02T08:53:48Z","article_processing_charge":"No","issue":"3","title":"Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition","publication":"Journal of the ACM","language":[{"iso":"eng"}],"abstract":[{"text":"The computation of the winning set for Büchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem is Õ(n ⋅ m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n ⋅ m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2)-time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n ⋅ m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m&gt;n4/3 an earlier bound of O(m ⋅ √m)). We then show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. Our algorithms are the first dynamic algorithms for this problem. We then consider another core graph theoretic problem in verification of probabilistic systems, namely computing the maximal end-component decomposition of a graph. We present two improved static algorithms for the maximal end-component decomposition problem. Our first algorithm is an O(m ⋅ √m)-time algorithm, and our second algorithm is an O(n2)-time algorithm which is obtained using the same technique as for alternating Büchi games. Thus, we obtain an O(min &amp;lcu;m ⋅ √m,n2})-time algorithm improving the long-standing O(n ⋅ m) time bound. Finally, we show how to maintain the maximal end-component decomposition of a graph under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time per edge insertion. Again, our algorithms are the first dynamic algorithms for this problem.","lang":"eng"}],"publication_status":"published","publisher":"ACM","date_published":"2014-05-01T00:00:00Z","department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":61,"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"ec_funded":1,"article_number":"a15","related_material":{"record":[{"id":"3165","relation":"earlier_version","status":"public"}]},"year":"2014","publist_id":"4883","citation":{"apa":"Chatterjee, K., &#38; Henzinger, M. H. (2014). Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/2597631\">https://doi.org/10.1145/2597631</a>","short":"K. Chatterjee, M.H. Henzinger, Journal of the ACM 61 (2014).","ama":"Chatterjee K, Henzinger MH. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. <i>Journal of the ACM</i>. 2014;61(3). doi:<a href=\"https://doi.org/10.1145/2597631\">10.1145/2597631</a>","ieee":"K. Chatterjee and M. H. Henzinger, “Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition,” <i>Journal of the ACM</i>, vol. 61, no. 3. ACM, 2014.","chicago":"Chatterjee, Krishnendu, and Monika H Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” <i>Journal of the ACM</i>. ACM, 2014. <a href=\"https://doi.org/10.1145/2597631\">https://doi.org/10.1145/2597631</a>.","mla":"Chatterjee, Krishnendu, and Monika H. Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” <i>Journal of the ACM</i>, vol. 61, no. 3, a15, ACM, 2014, doi:<a href=\"https://doi.org/10.1145/2597631\">10.1145/2597631</a>.","ista":"Chatterjee K, Henzinger MH. 2014. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 61(3), a15."},"date_created":"2018-12-11T11:55:57Z","doi":"10.1145/2597631","_id":"2141"},{"language":[{"iso":"eng"}],"intvolume":"      8573","oa":1,"date_updated":"2023-02-23T12:24:48Z","issue":"Part 2","title":"The complexity of ergodic mean payoff games","alternative_title":["LNCS"],"status":"public","type":"conference","conference":{"name":"ICST: International Conference on Software Testing, Verification and Validation","start_date":"2014-07-08","location":"Copenhagen, Denmark","end_date":"2014-07-11"},"month":"01","oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/1404.5734","open_access":"1"}],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"}],"arxiv":1,"doi":"10.1007/978-3-662-43951-7_11","_id":"2162","ec_funded":1,"related_material":{"record":[{"id":"5404","relation":"earlier_version","status":"public"}]},"year":"2014","publist_id":"4822","citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Ergodic Mean Payoff Games,” 8573:122–33. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">https://doi.org/10.1007/978-3-662-43951-7_11</a>.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Mean Payoff Games</i>. Vol. 8573, no. Part 2, Springer, 2014, pp. 122–33, doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">10.1007/978-3-662-43951-7_11</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The complexity of ergodic mean payoff games. ICST: International Conference on Software Testing, Verification and Validation, LNCS, vol. 8573, 122–133.","short":"K. Chatterjee, R. Ibsen-Jensen, in:, Springer, 2014, pp. 122–133.","ama":"Chatterjee K, Ibsen-Jensen R. The complexity of ergodic mean payoff games. In: Vol 8573. Springer; 2014:122-133. doi:<a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">10.1007/978-3-662-43951-7_11</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The complexity of ergodic mean payoff games,” presented at the ICST: International Conference on Software Testing, Verification and Validation, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 122–133.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). The complexity of ergodic mean payoff games (Vol. 8573, pp. 122–133). Presented at the ICST: International Conference on Software Testing, Verification and Validation, Copenhagen, Denmark: Springer. <a href=\"https://doi.org/10.1007/978-3-662-43951-7_11\">https://doi.org/10.1007/978-3-662-43951-7_11</a>"},"date_created":"2018-12-11T11:56:04Z","publisher":"Springer","date_published":"2014-01-01T00:00:00Z","page":"122 - 133","department":[{"_id":"KrCh"}],"volume":8573,"quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"name":"Game Theory","call_identifier":"FWF","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1404.5734"]},"abstract":[{"text":"We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lies in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP ∩ coNP is the long-standing best known bound). We present a variant of the strategy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existential theory of the reals, and establish square-root sum hardness for a related class of games.","lang":"eng"}],"publication_status":"published"}]