[{"type":"journal_article","status":"public","pmid":1,"author":[{"full_name":"Reiter, Johannes","first_name":"Johannes","orcid":"0000-0002-0170-7353","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter"},{"first_name":"Ayush","full_name":"Kanodia, Ayush","last_name":"Kanodia"},{"first_name":"Raghav","full_name":"Gupta, Raghav","last_name":"Gupta"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"15","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4528522/","open_access":"1"}],"oa_version":"Submitted Version","month":"07","language":[{"iso":"eng"}],"publication":"Proceedings of the Royal Society of London Series B Biological Sciences","title":"Biological auctions with multiple rewards","article_processing_charge":"No","issue":"1812","oa":1,"date_updated":"2023-09-07T11:40:43Z","intvolume":"       282","scopus_import":1,"project":[{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"volume":282,"quality_controlled":"1","department":[{"_id":"KrCh"}],"date_published":"2015-07-15T00:00:00Z","publisher":"Royal Society","publication_status":"published","abstract":[{"lang":"eng","text":"The competition for resources among cells, individuals or species is a fundamental characteristic of evolution. Biological all-pay auctions have been used to model situations where multiple individuals compete for a single resource. However, in many situations multiple resources with various values exist and single reward auctions are not applicable. We generalize the model to multiple rewards and study the evolution of strategies. In biological all-pay auctions the bid of an individual corresponds to its strategy and is equivalent to its payment in the auction. The decreasingly ordered rewards are distributed according to the decreasingly ordered bids of the participating individuals. The reproductive success of an individual is proportional to its fitness given by the sum of the rewards won minus its payments. Hence, successful bidding strategies spread in the population. We find that the results for the multiple reward case are very different from the single reward case. While the mixed strategy equilibrium in the single reward case with more than two players consists of mostly low-bidding individuals, we show that the equilibrium can convert to many high-bidding individuals and a few low-bidding individuals in the multiple reward case. Some reward values lead to a specialization among the individuals where one subpopulation competes for the rewards and the other subpopulation largely avoids costly competitions. Whether the mixed strategy equilibrium is an evolutionarily stable strategy (ESS) depends on the specific values of the rewards."}],"external_id":{"pmid":["26180069"]},"article_type":"original","_id":"1709","doi":"10.1098/rspb.2015.1041","citation":{"apa":"Reiter, J., Kanodia, A., Gupta, R., Nowak, M., &#38; Chatterjee, K. (2015). Biological auctions with multiple rewards. <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. Royal Society. <a href=\"https://doi.org/10.1098/rspb.2015.1041\">https://doi.org/10.1098/rspb.2015.1041</a>","ista":"Reiter J, Kanodia A, Gupta R, Nowak M, Chatterjee K. 2015. Biological auctions with multiple rewards. Proceedings of the Royal Society of London Series B Biological Sciences. 282(1812).","chicago":"Reiter, Johannes, Ayush Kanodia, Raghav Gupta, Martin Nowak, and Krishnendu Chatterjee. “Biological Auctions with Multiple Rewards.” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. Royal Society, 2015. <a href=\"https://doi.org/10.1098/rspb.2015.1041\">https://doi.org/10.1098/rspb.2015.1041</a>.","mla":"Reiter, Johannes, et al. “Biological Auctions with Multiple Rewards.” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>, vol. 282, no. 1812, Royal Society, 2015, doi:<a href=\"https://doi.org/10.1098/rspb.2015.1041\">10.1098/rspb.2015.1041</a>.","short":"J. Reiter, A. Kanodia, R. Gupta, M. Nowak, K. Chatterjee, Proceedings of the Royal Society of London Series B Biological Sciences 282 (2015).","ama":"Reiter J, Kanodia A, Gupta R, Nowak M, Chatterjee K. Biological auctions with multiple rewards. <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>. 2015;282(1812). doi:<a href=\"https://doi.org/10.1098/rspb.2015.1041\">10.1098/rspb.2015.1041</a>","ieee":"J. Reiter, A. Kanodia, R. Gupta, M. Nowak, and K. Chatterjee, “Biological auctions with multiple rewards,” <i>Proceedings of the Royal Society of London Series B Biological Sciences</i>, vol. 282, no. 1812. Royal Society, 2015."},"publist_id":"5425","date_created":"2018-12-11T11:53:35Z","year":"2015","acknowledgement":"This work was supported by grants from the John Templeton Foundation, ERC Start Grant (279307: Graph Games), FWF NFN Grant (No S11407N23 RiSE/SHiNE), FWF Grant (No P23499N23) and a Microsoft faculty fellows award.","related_material":{"record":[{"id":"1400","relation":"dissertation_contains","status":"public"}]}},{"date_published":"2015-01-15T00:00:00Z","publisher":"IEEE","quality_controlled":"1","volume":2015,"department":[{"_id":"KrCh"}],"page":"118 - 127","publication_status":"published","abstract":[{"lang":"eng","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 task set 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 Dover, that have been proposed in the past, for various task sets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are task sets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application."}],"_id":"1714","doi":"10.1109/RTSS.2014.9","year":"2015","date_created":"2018-12-11T11:53:37Z","publist_id":"5417","citation":{"ieee":"K. Chatterjee, A. Pavlogiannis, A. Kößler, and U. Schmid, “A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks,” in <i>Real-Time Systems Symposium</i>, Rome, Italy, 2015, vol. 2015, no. January, pp. 118–127.","ama":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In: <i>Real-Time Systems Symposium</i>. Vol 2015. IEEE; 2015:118-127. doi:<a href=\"https://doi.org/10.1109/RTSS.2014.9\">10.1109/RTSS.2014.9</a>","short":"K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, in:, Real-Time Systems Symposium, IEEE, 2015, pp. 118–127.","ista":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. 2015. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. Real-Time Systems Symposium. RTSS: Real-Time Systems Symposium vol. 2015, 118–127.","mla":"Chatterjee, Krishnendu, et al. “A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks.” <i>Real-Time Systems Symposium</i>, vol. 2015, no. January, IEEE, 2015, pp. 118–27, doi:<a href=\"https://doi.org/10.1109/RTSS.2014.9\">10.1109/RTSS.2014.9</a>.","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, Alexander Kößler, and Ulrich Schmid. “A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks.” In <i>Real-Time Systems Symposium</i>, 2015:118–27. IEEE, 2015. <a href=\"https://doi.org/10.1109/RTSS.2014.9\">https://doi.org/10.1109/RTSS.2014.9</a>.","apa":"Chatterjee, K., Pavlogiannis, A., Kößler, A., &#38; Schmid, U. (2015). A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. In <i>Real-Time Systems Symposium</i> (Vol. 2015, pp. 118–127). Rome, Italy: IEEE. <a href=\"https://doi.org/10.1109/RTSS.2014.9\">https://doi.org/10.1109/RTSS.2014.9</a>"},"related_material":{"record":[{"id":"5423","relation":"earlier_version","status":"public"},{"status":"public","relation":"dissertation_contains","id":"821"}]},"status":"public","type":"conference","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas"},{"first_name":"Alexander","full_name":"Kößler, Alexander","last_name":"Kößler"},{"full_name":"Schmid, Ulrich","first_name":"Ulrich","last_name":"Schmid"}],"month":"01","conference":{"name":"RTSS: Real-Time Systems Symposium","start_date":"2014-12-02","location":"Rome, Italy","end_date":"2014-12-05"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"15","oa_version":"None","language":[{"iso":"eng"}],"publication":"Real-Time Systems Symposium","issue":"January","article_processing_charge":"No","date_updated":"2023-09-07T12:01:59Z","title":"A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks","intvolume":"      2015","scopus_import":1},{"status":"public","type":"journal_article","day":"01","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1006.0673"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","month":"12","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Doyen","full_name":"Doyen, Laurent","first_name":"Laurent"},{"last_name":"Gimbert","first_name":"Hugo","full_name":"Gimbert, Hugo"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A","full_name":"Henzinger, Thomas A"}],"publication":"Information and Computation","language":[{"iso":"eng"}],"scopus_import":1,"intvolume":"       245","title":"Randomness for free","date_updated":"2023-02-23T11:45:42Z","oa":1,"issue":"12","page":"3 - 16","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"volume":245,"quality_controlled":"1","publisher":"Elsevier","date_published":"2015-12-01T00:00:00Z","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","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"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"name":"COMponent-Based Embedded Systems design Techniques","call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","grant_number":"215543"},{"call_identifier":"FP7","name":"Design for Embedded Systems","grant_number":"214373","_id":"25F1337C-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"}],"abstract":[{"lang":"eng","text":"We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games. "}],"publication_status":"published","doi":"10.1016/j.ic.2015.06.003","_id":"1731","ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","id":"3856","status":"public"}]},"date_created":"2018-12-11T11:53:42Z","publist_id":"5395","citation":{"ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger, “Randomness for free,” <i>Information and Computation</i>, vol. 245, no. 12. Elsevier, pp. 3–16, 2015.","ama":"Chatterjee K, Doyen L, Gimbert H, Henzinger TA. Randomness for free. <i>Information and Computation</i>. 2015;245(12):3-16. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">10.1016/j.ic.2015.06.003</a>","short":"K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, Information and Computation 245 (2015) 3–16.","ista":"Chatterjee K, Doyen L, Gimbert H, Henzinger TA. 2015. Randomness for free. Information and Computation. 245(12), 3–16.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Thomas A Henzinger. “Randomness for Free.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">https://doi.org/10.1016/j.ic.2015.06.003</a>.","mla":"Chatterjee, Krishnendu, et al. “Randomness for Free.” <i>Information and Computation</i>, vol. 245, no. 12, Elsevier, 2015, pp. 3–16, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">10.1016/j.ic.2015.06.003</a>.","apa":"Chatterjee, K., Doyen, L., Gimbert, H., &#38; Henzinger, T. A. (2015). Randomness for free. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">https://doi.org/10.1016/j.ic.2015.06.003</a>"},"year":"2015"},{"external_id":{"arxiv":["1409.3360"]},"abstract":[{"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.","lang":"eng"}],"publication_status":"published","publisher":"IEEE","date_published":"2015-01-01T00:00:00Z","page":"325 - 330","department":[{"_id":"KrCh"}],"quality_controlled":"1","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"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}],"ec_funded":1,"related_material":{"record":[{"status":"public","id":"5424","relation":"earlier_version"},{"relation":"earlier_version","id":"5426","status":"public"}]},"year":"2015","citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications,” 325–30. IEEE, 2015. <a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">https://doi.org/10.1109/ICRA.2015.7139019</a>.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. ICRA: International Conference on Robotics and Automation, 325–330.","mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IEEE, 2015, pp. 325–30, doi:<a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">10.1109/ICRA.2015.7139019</a>.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. In: IEEE; 2015:325-330. doi:<a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">10.1109/ICRA.2015.7139019</a>","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Qualitative analysis of POMDPs with temporal logic specifications for robotics applications,” presented at the ICRA: International Conference on Robotics and Automation, Seattle, WA, United States, 2015, pp. 325–330.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, IEEE, 2015, pp. 325–330.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2015). Qualitative analysis of POMDPs with temporal logic specifications for robotics applications (pp. 325–330). Presented at the ICRA: International Conference on Robotics and Automation, Seattle, WA, United States: IEEE. <a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">https://doi.org/10.1109/ICRA.2015.7139019</a>"},"publist_id":"5394","date_created":"2018-12-11T11:53:43Z","doi":"10.1109/ICRA.2015.7139019","_id":"1732","conference":{"start_date":"2015-05-26","name":"ICRA: International Conference on Robotics and Automation","end_date":"2015-05-30","location":"Seattle, WA, United States"},"month":"01","oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/1409.3360","open_access":"1"}],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Chmelik, Martin"},{"last_name":"Gupta","first_name":"Raghav","full_name":"Gupta, Raghav"},{"first_name":"Ayush","full_name":"Kanodia, Ayush","last_name":"Kanodia"}],"arxiv":1,"type":"conference","status":"public","scopus_import":1,"oa":1,"date_updated":"2023-02-23T12:25:52Z","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","language":[{"iso":"eng"}]},{"page":"3496-3502","department":[{"_id":"KrCh"}],"volume":5,"quality_controlled":"1","publisher":"AAAI Press","date_published":"2015-06-01T00:00:00Z","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}],"external_id":{"arxiv":["1411.3880"]},"abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objec- tive we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present ap- proximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst- case running time of our algorithm is double exponential, we present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples."}],"publication_status":"published","_id":"1820","ec_funded":1,"related_material":{"record":[{"status":"public","relation":"later_version","id":"1529"}]},"publist_id":"5286","date_created":"2018-12-11T11:54:11Z","citation":{"apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2015). Optimal cost almost-sure reachability in POMDPs. In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i> (Vol. 5, pp. 3496–3502). Austin, TX, USA: AAAI Press.","mla":"Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.” <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, vol. 5, AAAI Press, 2015, pp. 3496–502.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Optimal cost almost-sure reachability in POMDPs. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence . IAAI: Innovative Applications of Artificial Intelligence, Artifical Intelligence, vol. 5, 3496–3502.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Optimal Cost Almost-Sure Reachability in POMDPs.” In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, 5:3496–3502. AAAI Press, 2015.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability in POMDPs. In: <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>. Vol 5. AAAI Press; 2015:3496-3502.","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure reachability in POMDPs,” in <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, Austin, TX, USA, 2015, vol. 5, pp. 3496–3502.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp. 3496–3502."},"acknowledgement":" The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","year":"2015","alternative_title":["Artifical Intelligence"],"type":"conference","status":"public","oa_version":"Preprint","day":"01","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1411.3880"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"name":"IAAI: Innovative Applications of Artificial Intelligence","start_date":"2015-01-25","location":"Austin, TX, USA","end_date":"2015-01-30"},"month":"06","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Chmelik, Martin","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik"},{"full_name":"Gupta, Raghav","first_name":"Raghav","last_name":"Gupta"},{"first_name":"Ayush","full_name":"Kanodia, Ayush","last_name":"Kanodia"}],"arxiv":1,"publication":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence ","language":[{"iso":"eng"}],"intvolume":"         5","scopus_import":1,"title":"Optimal cost almost-sure reachability in POMDPs","date_updated":"2023-02-23T10:02:57Z","oa":1},{"publication_status":"published","abstract":[{"lang":"eng","text":"Synthesis of program parts is particularly useful for concurrent systems. However, most approaches do not support common design tasks, like modifying a single process without having to re-synthesize or verify the whole system. Assume-guarantee synthesis (AGS) provides robustness against modifications of system parts, but thus far has been limited to the perfect information setting. This means that local variables cannot be hidden from other processes, which renders synthesis results cumbersome or even impossible to realize.We resolve this shortcoming by defining AGS under partial information. We analyze the complexity and decidability in different settings, showing that the problem has a high worstcase complexity and is undecidable in many interesting cases. Based on these observations, we present a pragmatic algorithm based on bounded synthesis, and demonstrate its practical applicability on several examples."}],"project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"}],"volume":9035,"page":"517 - 532","department":[{"_id":"KrCh"}],"date_published":"2015-01-01T00:00:00Z","publisher":"Springer","publist_id":"5264","date_created":"2018-12-11T11:54:17Z","citation":{"apa":"Bloem, R., Chatterjee, K., Jacobs, S., &#38; Könighofer, R. (2015). Assume-guarantee synthesis for concurrent reactive programs with partial information (Vol. 9035, pp. 517–532). Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, London, United Kingdom: Springer. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">https://doi.org/10.1007/978-3-662-46681-0_50</a>","ieee":"R. Bloem, K. Chatterjee, S. Jacobs, and R. Könighofer, “Assume-guarantee synthesis for concurrent reactive programs with partial information,” presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, London, United Kingdom, 2015, vol. 9035, pp. 517–532.","ama":"Bloem R, Chatterjee K, Jacobs S, Könighofer R. Assume-guarantee synthesis for concurrent reactive programs with partial information. In: Vol 9035. Springer; 2015:517-532. doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">10.1007/978-3-662-46681-0_50</a>","short":"R. Bloem, K. Chatterjee, S. Jacobs, R. Könighofer, in:, Springer, 2015, pp. 517–532.","chicago":"Bloem, Roderick, Krishnendu Chatterjee, Swen Jacobs, and Robert Könighofer. “Assume-Guarantee Synthesis for Concurrent Reactive Programs with Partial Information,” 9035:517–32. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">https://doi.org/10.1007/978-3-662-46681-0_50</a>.","mla":"Bloem, Roderick, et al. <i>Assume-Guarantee Synthesis for Concurrent Reactive Programs with Partial Information</i>. Vol. 9035, Springer, 2015, pp. 517–32, doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">10.1007/978-3-662-46681-0_50</a>.","ista":"Bloem R, Chatterjee K, Jacobs S, Könighofer R. 2015. Assume-guarantee synthesis for concurrent reactive programs with partial information. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 9035, 517–532."},"year":"2015","acknowledgement":"This work was supported by the Austrian Science Fund (FWF) through the research network RiSE (S11406-N23, S11407-N23) and grant nr. P23499-N23, by the European Commission through an ERC Start grant (279307: Graph Games) and project STANCE (317753), as well as by the German Research Foundation (DFG) through SFB/TR 14 AVACS and project ASDPS(JA 2357/2-1).","ec_funded":1,"_id":"1838","doi":"10.1007/978-3-662-46681-0_50","author":[{"full_name":"Bloem, Roderick","first_name":"Roderick","last_name":"Bloem"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Jacobs","first_name":"Swen","full_name":"Jacobs, Swen"},{"last_name":"Könighofer","first_name":"Robert","full_name":"Könighofer, Robert"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1411.4604"}],"oa_version":"Preprint","day":"01","month":"01","conference":{"location":"London, United Kingdom","end_date":"2015-04-18","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2015-04-11"},"status":"public","type":"conference","alternative_title":["LNCS"],"title":"Assume-guarantee synthesis for concurrent reactive programs with partial information","oa":1,"date_updated":"2021-01-12T06:53:32Z","scopus_import":1,"intvolume":"      9035","language":[{"iso":"eng"}]},{"intvolume":"      9035","title":"Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives","oa":1,"date_updated":"2020-01-21T13:18:52Z","language":[{"iso":"eng"}],"day":"01","main_file_link":[{"url":"http://arxiv.org/abs/1501.03093","open_access":"1"}],"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2015-04-11","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","end_date":"2015-04-18","location":"London, United Kingdom"},"month":"01","author":[{"full_name":"Brázdil, Tomáš","first_name":"Tomáš","last_name":"Brázdil"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Forejt","full_name":"Forejt, Vojtěch","first_name":"Vojtěch"},{"last_name":"Kučera","first_name":"Antonín","full_name":"Kučera, Antonín"}],"alternative_title":["LNCS"],"status":"public","type":"conference","ec_funded":1,"publist_id":"5263","date_created":"2018-12-11T11:54:18Z","citation":{"ista":"Brázdil T, Chatterjee K, Forejt V, Kučera A. 2015. Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives. 9035, 181–187.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Multigain: A Controller Synthesis Tool for MDPs with Multiple Mean-Payoff Objectives.” Lecture Notes in Computer Science. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">https://doi.org/10.1007/978-3-662-46681-0_12</a>.","mla":"Brázdil, Tomáš, et al. <i>Multigain: A Controller Synthesis Tool for MDPs with Multiple Mean-Payoff Objectives</i>. Vol. 9035, Springer, 2015, pp. 181–87, doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">10.1007/978-3-662-46681-0_12</a>.","ieee":"T. Brázdil, K. Chatterjee, V. Forejt, and A. Kučera, “Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives,” vol. 9035. Springer, pp. 181–187, 2015.","ama":"Brázdil T, Chatterjee K, Forejt V, Kučera A. Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives. 2015;9035:181-187. doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">10.1007/978-3-662-46681-0_12</a>","short":"T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, 9035 (2015) 181–187.","apa":"Brázdil, T., Chatterjee, K., Forejt, V., &#38; Kučera, A. (2015). Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives. Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, London, United Kingdom: Springer. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">https://doi.org/10.1007/978-3-662-46681-0_12</a>"},"year":"2015","doi":"10.1007/978-3-662-46681-0_12","_id":"1839","abstract":[{"text":"We present MultiGain, a tool to synthesize strategies for Markov decision processes (MDPs) with multiple mean-payoff objectives. Our models are described in PRISM, and our tool uses the existing interface and simulator of PRISM. Our tool extends PRISM by adding novel algorithms for multiple mean-payoff objectives, and also provides features such as (i) generating strategies and exploring them for simulation, and checking them with respect to other properties; and (ii) generating an approximate Pareto curve for two mean-payoff objectives. In addition, we present a new practical algorithm for the analysis of MDPs with multiple mean-payoff objectives under memoryless strategies.","lang":"eng"}],"series_title":"Lecture Notes in Computer Science","publication_status":"published","page":"181 - 187","department":[{"_id":"KrCh"}],"volume":9035,"quality_controlled":"1","publisher":"Springer","date_published":"2015-01-01T00: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":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}]},{"title":"Refinement checking on parametric modal transition systems","oa":1,"date_updated":"2021-01-12T06:53:35Z","article_processing_charge":"No","issue":"2-3","intvolume":"        52","has_accepted_license":"1","scopus_import":1,"language":[{"iso":"eng"}],"publication":"Acta Informatica","author":[{"last_name":"Beneš","full_name":"Beneš, Nikola","first_name":"Nikola"},{"orcid":"0000-0002-8122-2881","last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","first_name":"Jan"},{"full_name":"Larsen, Kim","first_name":"Kim","last_name":"Larsen"},{"last_name":"Möller","full_name":"Möller, Mikael","first_name":"Mikael"},{"full_name":"Sickert, Salomon","first_name":"Salomon","last_name":"Sickert"},{"last_name":"Srba","full_name":"Srba, Jiří","first_name":"Jiří"}],"day":"01","oa_version":"Submitted Version","file":[{"creator":"dernst","relation":"main_file","file_size":488482,"access_level":"open_access","content_type":"application/pdf","checksum":"fb4037ddc4fc05f33080dd3547ede350","file_name":"2015_ActaInfo_Benes.pdf","file_id":"7854","date_created":"2020-05-15T08:57:44Z","date_updated":"2020-07-14T12:45:19Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"04","type":"journal_article","status":"public","date_created":"2018-12-11T11:54:20Z","citation":{"ama":"Beneš N, Kretinsky J, Larsen K, Möller M, Sickert S, Srba J. Refinement checking on parametric modal transition systems. <i>Acta Informatica</i>. 2015;52(2-3):269-297. doi:<a href=\"https://doi.org/10.1007/s00236-015-0215-4\">10.1007/s00236-015-0215-4</a>","ieee":"N. Beneš, J. Kretinsky, K. Larsen, M. Möller, S. Sickert, and J. Srba, “Refinement checking on parametric modal transition systems,” <i>Acta Informatica</i>, vol. 52, no. 2–3. Springer, pp. 269–297, 2015.","short":"N. Beneš, J. Kretinsky, K. Larsen, M. Möller, S. Sickert, J. Srba, Acta Informatica 52 (2015) 269–297.","ista":"Beneš N, Kretinsky J, Larsen K, Möller M, Sickert S, Srba J. 2015. Refinement checking on parametric modal transition systems. Acta Informatica. 52(2–3), 269–297.","mla":"Beneš, Nikola, et al. “Refinement Checking on Parametric Modal Transition Systems.” <i>Acta Informatica</i>, vol. 52, no. 2–3, Springer, 2015, pp. 269–97, doi:<a href=\"https://doi.org/10.1007/s00236-015-0215-4\">10.1007/s00236-015-0215-4</a>.","chicago":"Beneš, Nikola, Jan Kretinsky, Kim Larsen, Mikael Möller, Salomon Sickert, and Jiří Srba. “Refinement Checking on Parametric Modal Transition Systems.” <i>Acta Informatica</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00236-015-0215-4\">https://doi.org/10.1007/s00236-015-0215-4</a>.","apa":"Beneš, N., Kretinsky, J., Larsen, K., Möller, M., Sickert, S., &#38; Srba, J. (2015). Refinement checking on parametric modal transition systems. <i>Acta Informatica</i>. Springer. <a href=\"https://doi.org/10.1007/s00236-015-0215-4\">https://doi.org/10.1007/s00236-015-0215-4</a>"},"publist_id":"5255","year":"2015","ec_funded":1,"file_date_updated":"2020-07-14T12:45:19Z","_id":"1846","article_type":"original","doi":"10.1007/s00236-015-0215-4","publication_status":"published","abstract":[{"lang":"eng","text":"Modal transition systems (MTS) is a well-studied specification formalism of reactive systems supporting a step-wise refinement methodology. Despite its many advantages, the formalism as well as its currently known extensions are incapable of expressing some practically needed aspects in the refinement process like exclusive, conditional and persistent choices. We introduce a new model called parametric modal transition systems (PMTS) together with a general modal refinement notion that overcomes many of the limitations. We investigate the computational complexity of modal and thorough refinement checking on PMTS and its subclasses and provide a direct encoding of the modal refinement problem into quantified Boolean formulae, allowing us to employ state-of-the-art QBF solvers for modal refinement checking. The experiments we report on show that the feasibility of refinement checking is more influenced by the degree of nondeterminism rather than by the syntactic restrictions on the types of formulae allowed in the description of the PMTS."}],"ddc":["000"],"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","call_identifier":"FP7","name":"Quantitative Reactive Modeling"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"}],"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"page":"269 - 297","quality_controlled":"1","volume":52,"publisher":"Springer","date_published":"2015-04-01T00:00:00Z"},{"file_date_updated":"2020-07-14T12:45:19Z","_id":"1851","article_type":"original","doi":"10.1111/evo.12618","year":"2015","date_created":"2018-12-11T11:54:21Z","citation":{"apa":"Priklopil, T., Kisdi, E., &#38; Gyllenberg, M. (2015). Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating. <i>Evolution</i>. Wiley. <a href=\"https://doi.org/10.1111/evo.12618\">https://doi.org/10.1111/evo.12618</a>","chicago":"Priklopil, Tadeas, Eva Kisdi, and Mats Gyllenberg. “Evolutionarily Stable Mating Decisions for Sequentially Searching Females and the Stability of Reproductive Isolation by Assortative Mating.” <i>Evolution</i>. Wiley, 2015. <a href=\"https://doi.org/10.1111/evo.12618\">https://doi.org/10.1111/evo.12618</a>.","ista":"Priklopil T, Kisdi E, Gyllenberg M. 2015. Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating. Evolution. 69(4), 1015–1026.","mla":"Priklopil, Tadeas, et al. “Evolutionarily Stable Mating Decisions for Sequentially Searching Females and the Stability of Reproductive Isolation by Assortative Mating.” <i>Evolution</i>, vol. 69, no. 4, Wiley, 2015, pp. 1015–26, doi:<a href=\"https://doi.org/10.1111/evo.12618\">10.1111/evo.12618</a>.","ieee":"T. Priklopil, E. Kisdi, and M. Gyllenberg, “Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating,” <i>Evolution</i>, vol. 69, no. 4. Wiley, pp. 1015–1026, 2015.","ama":"Priklopil T, Kisdi E, Gyllenberg M. Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating. <i>Evolution</i>. 2015;69(4):1015-1026. doi:<a href=\"https://doi.org/10.1111/evo.12618\">10.1111/evo.12618</a>","short":"T. Priklopil, E. Kisdi, M. Gyllenberg, Evolution 69 (2015) 1015–1026."},"publist_id":"5249","ec_funded":1,"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"publisher":"Wiley","date_published":"2015-02-09T00:00:00Z","page":"1015 - 1026","department":[{"_id":"NiBa"},{"_id":"KrCh"}],"volume":69,"quality_controlled":"1","publication_status":"published","ddc":["570"],"external_id":{"pmid":["25662095"]},"abstract":[{"text":"We consider mating strategies for females who search for males sequentially during a season of limited length. We show that the best strategy rejects a given male type if encountered before a time-threshold but accepts him after. For frequency-independent benefits, we obtain the optimal time-thresholds explicitly for both discrete and continuous distributions of males, and allow for mistakes being made in assessing the correct male type. When the benefits are indirect (genes for the offspring) and the population is under frequency-dependent ecological selection, the benefits depend on the mating strategy of other females as well. This case is particularly relevant to speciation models that seek to explore the stability of reproductive isolation by assortative mating under frequency-dependent ecological selection. We show that the indirect benefits are to be quantified by the reproductive values of couples, and describe how the evolutionarily stable time-thresholds can be found. We conclude with an example based on the Levene model, in which we analyze the evolutionarily stable assortative mating strategies and the strength of reproductive isolation provided by them.","lang":"eng"}],"language":[{"iso":"eng"}],"publication":"Evolution","oa":1,"date_updated":"2022-06-07T10:52:37Z","issue":"4","article_processing_charge":"No","title":"Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating","scopus_import":"1","intvolume":"        69","has_accepted_license":"1","pmid":1,"type":"journal_article","status":"public","author":[{"full_name":"Priklopil, Tadeas","first_name":"Tadeas","id":"3C869AA0-F248-11E8-B48F-1D18A9856A87","last_name":"Priklopil"},{"last_name":"Kisdi","full_name":"Kisdi, Eva","first_name":"Eva"},{"last_name":"Gyllenberg","full_name":"Gyllenberg, Mats","first_name":"Mats"}],"publication_identifier":{"eissn":["1558-5646"],"issn":["0014-3820"]},"month":"02","oa_version":"Submitted Version","day":"09","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","file_size":967214,"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2015_Evolution_Priklopil.pdf","file_id":"7855","checksum":"1e8be0b1d7598a78cd2623d8ee8e7798","date_updated":"2020-07-14T12:45:19Z","date_created":"2020-05-15T09:05:34Z"}]},{"doi":"10.1145/2699430","_id":"1856","ec_funded":1,"article_number":"9","related_material":{"record":[{"status":"public","id":"3864","relation":"earlier_version"}]},"date_created":"2018-12-11T11:54:23Z","citation":{"ista":"Chatterjee K, Henzinger TA, Jobstmann B, Singh R. 2015. Measuring and synthesizing systems in probabilistic environments. Journal of the ACM. 62(1), 9.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Barbara Jobstmann, and Rohit Singh. “Measuring and Synthesizing Systems in Probabilistic Environments.” <i>Journal of the ACM</i>. ACM, 2015. <a href=\"https://doi.org/10.1145/2699430\">https://doi.org/10.1145/2699430</a>.","mla":"Chatterjee, Krishnendu, et al. “Measuring and Synthesizing Systems in Probabilistic Environments.” <i>Journal of the ACM</i>, vol. 62, no. 1, 9, ACM, 2015, doi:<a href=\"https://doi.org/10.1145/2699430\">10.1145/2699430</a>.","short":"K. Chatterjee, T.A. Henzinger, B. Jobstmann, R. Singh, Journal of the ACM 62 (2015).","ama":"Chatterjee K, Henzinger TA, Jobstmann B, Singh R. Measuring and synthesizing systems in probabilistic environments. <i>Journal of the ACM</i>. 2015;62(1). doi:<a href=\"https://doi.org/10.1145/2699430\">10.1145/2699430</a>","ieee":"K. Chatterjee, T. A. Henzinger, B. Jobstmann, and R. Singh, “Measuring and synthesizing systems in probabilistic environments,” <i>Journal of the ACM</i>, vol. 62, no. 1. ACM, 2015.","apa":"Chatterjee, K., Henzinger, T. A., Jobstmann, B., &#38; Singh, R. (2015). Measuring and synthesizing systems in probabilistic environments. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/2699430\">https://doi.org/10.1145/2699430</a>"},"publist_id":"5244","year":"2015","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"volume":62,"quality_controlled":"1","publisher":"ACM","date_published":"2015-02-01T00:00:00Z","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","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"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"abstract":[{"text":"The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under a probabilistic assumption about the possible inputs, such a preference order is naturally expressed by a weighted automaton, which assigns to each word a value, such that a system is preferred if it generates a higher expected value. We solve the following optimal synthesis problem: given an omega-regular specification, a Markov chain that describes the distribution of inputs, and a weighted automaton that measures how well a system satisfies the given specification under the input assumption, synthesize a system that optimizes the measured value. For safety specifications and quantitative measures that are defined by mean-payoff automata, the optimal synthesis problem reduces to finding a strategy in a Markov decision process (MDP) that is optimal for a long-run average reward objective, which can be achieved in polynomial time. For general omega-regular specifications along with mean-payoff automata, the solution rests on a new, polynomial-time algorithm for computing optimal strategies in MDPs with mean-payoff parity objectives. Our algorithm constructs optimal strategies that consist of two memoryless strategies and a counter. The counter is in general not bounded. To obtain a finite-state system, we show how to construct an ε-optimal strategy with a bounded counter, for all ε &gt; 0. Furthermore, we show how to decide in polynomial time if it is possible to construct an optimal finite-state system (i.e., a system without a counter) for a given specification. We have implemented our approach and the underlying algorithms in a tool that takes qualitative and quantitative specifications and automatically constructs a system that satisfies the qualitative specification and optimizes the quantitative specification, if such a system exists. We present some experimental results showing optimal systems that were automatically generated in this way.","lang":"eng"}],"publication_status":"published","publication":"Journal of the ACM","language":[{"iso":"eng"}],"intvolume":"        62","scopus_import":1,"title":"Measuring and synthesizing systems in probabilistic environments","oa":1,"date_updated":"2023-02-23T11:46:04Z","issue":"1","status":"public","type":"journal_article","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1004.0739","open_access":"1"}],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"02","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A"},{"last_name":"Jobstmann","full_name":"Jobstmann, Barbara","first_name":"Barbara"},{"last_name":"Singh","full_name":"Singh, Rohit","first_name":"Rohit"}]},{"doi":"10.1016/j.artint.2014.12.009","_id":"1873","citation":{"short":"K. Chatterjee, M. Chmelik, Artificial Intelligence 221 (2015) 46–72.","ama":"Chatterjee K, Chmelik M. POMDPs under probabilistic semantics. <i>Artificial Intelligence</i>. 2015;221:46-72. doi:<a href=\"https://doi.org/10.1016/j.artint.2014.12.009\">10.1016/j.artint.2014.12.009</a>","ieee":"K. Chatterjee and M. Chmelik, “POMDPs under probabilistic semantics,” <i>Artificial Intelligence</i>, vol. 221. Elsevier, pp. 46–72, 2015.","ista":"Chatterjee K, Chmelik M. 2015. POMDPs under probabilistic semantics. Artificial Intelligence. 221, 46–72.","mla":"Chatterjee, Krishnendu, and Martin Chmelik. “POMDPs under Probabilistic Semantics.” <i>Artificial Intelligence</i>, vol. 221, Elsevier, 2015, pp. 46–72, doi:<a href=\"https://doi.org/10.1016/j.artint.2014.12.009\">10.1016/j.artint.2014.12.009</a>.","chicago":"Chatterjee, Krishnendu, and Martin Chmelik. “POMDPs under Probabilistic Semantics.” <i>Artificial Intelligence</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.artint.2014.12.009\">https://doi.org/10.1016/j.artint.2014.12.009</a>.","apa":"Chatterjee, K., &#38; Chmelik, M. (2015). POMDPs under probabilistic semantics. <i>Artificial Intelligence</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.artint.2014.12.009\">https://doi.org/10.1016/j.artint.2014.12.009</a>"},"date_created":"2018-12-11T11:54:28Z","publist_id":"5224","year":"2015","volume":221,"quality_controlled":"1","department":[{"_id":"KrCh"}],"page":"46 - 72","date_published":"2015-04-01T00:00:00Z","publisher":"Elsevier","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated with every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) a quantitative constraint defines the set of paths where the payoff is at least a given threshold λ1ε(0,1]; and (ii) a qualitative constraint which is a special case of the quantitative constraint with λ1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraints are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We also present a prototype implementation of our EXPTIME algorithm and experimental results on several examples.","lang":"eng"}],"external_id":{"arxiv":["1408.2058"]},"publication_status":"published","publication":"Artificial Intelligence","language":[{"iso":"eng"}],"scopus_import":1,"intvolume":"       221","title":"POMDPs under probabilistic semantics","oa":1,"date_updated":"2021-01-12T06:53:46Z","type":"journal_article","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1408.2058","open_access":"1"}],"day":"01","month":"04","arxiv":1,"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Chmelik, Martin","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik"}]},{"intvolume":"      8997","scopus_import":1,"title":"Compositionality for quantitative specifications","date_updated":"2021-01-12T06:53:49Z","oa":1,"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"30","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.1256"}],"month":"01","conference":{"end_date":"2014-09-12","location":"Bertinoro, Italy","start_date":"2014-09-10","name":"FACS: Formal Aspects of Component Software"},"author":[{"full_name":"Fahrenberg, Uli","first_name":"Uli","last_name":"Fahrenberg"},{"full_name":"Kretinsky, Jan","first_name":"Jan","last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881"},{"last_name":"Legay","full_name":"Legay, Axel","first_name":"Axel"},{"full_name":"Traonouez, Louis","first_name":"Louis","last_name":"Traonouez"}],"status":"public","type":"conference","alternative_title":["LNCS"],"ec_funded":1,"citation":{"ista":"Fahrenberg U, Kretinsky J, Legay A, Traonouez L. 2015. Compositionality for quantitative specifications. FACS: Formal Aspects of Component Software, LNCS, vol. 8997, 306–324.","chicago":"Fahrenberg, Uli, Jan Kretinsky, Axel Legay, and Louis Traonouez. “Compositionality for Quantitative Specifications,” 8997:306–24. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-319-15317-9_19\">https://doi.org/10.1007/978-3-319-15317-9_19</a>.","mla":"Fahrenberg, Uli, et al. <i>Compositionality for Quantitative Specifications</i>. Vol. 8997, Springer, 2015, pp. 306–24, doi:<a href=\"https://doi.org/10.1007/978-3-319-15317-9_19\">10.1007/978-3-319-15317-9_19</a>.","ieee":"U. Fahrenberg, J. Kretinsky, A. Legay, and L. Traonouez, “Compositionality for quantitative specifications,” presented at the FACS: Formal Aspects of Component Software, Bertinoro, Italy, 2015, vol. 8997, pp. 306–324.","ama":"Fahrenberg U, Kretinsky J, Legay A, Traonouez L. Compositionality for quantitative specifications. In: Vol 8997. Springer; 2015:306-324. doi:<a href=\"https://doi.org/10.1007/978-3-319-15317-9_19\">10.1007/978-3-319-15317-9_19</a>","short":"U. Fahrenberg, J. Kretinsky, A. Legay, L. Traonouez, in:, Springer, 2015, pp. 306–324.","apa":"Fahrenberg, U., Kretinsky, J., Legay, A., &#38; Traonouez, L. (2015). Compositionality for quantitative specifications (Vol. 8997, pp. 306–324). Presented at the FACS: Formal Aspects of Component Software, Bertinoro, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-319-15317-9_19\">https://doi.org/10.1007/978-3-319-15317-9_19</a>"},"date_created":"2018-12-11T11:54:31Z","publist_id":"5216","year":"2015","acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) project S11402-N23 (RiSE), and by the Czech Science Foundation, grant No. P202/12/G061.","doi":"10.1007/978-3-319-15317-9_19","_id":"1882","abstract":[{"text":"We provide a framework for compositional and iterative design and verification of systems with quantitative information, such as rewards, time or energy. It is based on disjunctive modal transition systems where we allow actions to bear various types of quantitative information. Throughout the design process the actions can be further refined and the information made more precise. We show how to compute the results of standard operations on the systems, including the quotient (residual), which has not been previously considered for quantitative non-deterministic systems. Our quantitative framework has close connections to the modal nu-calculus and is compositional with respect to general notions of distances between systems and the standard operations.","lang":"eng"}],"publication_status":"published","volume":8997,"quality_controlled":"1","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"page":"306 - 324","date_published":"2015-01-30T00:00:00Z","publisher":"Springer","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","main_file_link":[{"url":"http://arxiv.org/abs/1407.4225","open_access":"1"}],"oa_version":"Preprint","month":"01","author":[{"last_name":"Bérard","full_name":"Bérard, Béatrice","first_name":"Béatrice"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Sznajder, Nathalie","first_name":"Nathalie","last_name":"Sznajder"}],"status":"public","type":"journal_article","scopus_import":1,"intvolume":"       115","title":"Probabilistic opacity for Markov decision processes","issue":"1","date_updated":"2021-01-12T06:54:52Z","oa":1,"publication":" Information Processing Letters","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers."}],"publication_status":"published","quality_controlled":"1","volume":115,"department":[{"_id":"KrCh"}],"page":"52 - 59","date_published":"2015-01-01T00:00:00Z","publisher":"Elsevier","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","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"ec_funded":1,"date_created":"2018-12-11T11:55:20Z","citation":{"short":"B. Bérard, K. Chatterjee, N. Sznajder,  Information Processing Letters 115 (2015) 52–59.","ama":"Bérard B, Chatterjee K, Sznajder N. Probabilistic opacity for Markov decision processes. <i> Information Processing Letters</i>. 2015;115(1):52-59. doi:<a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">10.1016/j.ipl.2014.09.001</a>","ieee":"B. Bérard, K. Chatterjee, and N. Sznajder, “Probabilistic opacity for Markov decision processes,” <i> Information Processing Letters</i>, vol. 115, no. 1. Elsevier, pp. 52–59, 2015.","chicago":"Bérard, Béatrice, Krishnendu Chatterjee, and Nathalie Sznajder. “Probabilistic Opacity for Markov Decision Processes.” <i> Information Processing Letters</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">https://doi.org/10.1016/j.ipl.2014.09.001</a>.","ista":"Bérard B, Chatterjee K, Sznajder N. 2015. Probabilistic opacity for Markov decision processes.  Information Processing Letters. 115(1), 52–59.","mla":"Bérard, Béatrice, et al. “Probabilistic Opacity for Markov Decision Processes.” <i> Information Processing Letters</i>, vol. 115, no. 1, Elsevier, 2015, pp. 52–59, doi:<a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">10.1016/j.ipl.2014.09.001</a>.","apa":"Bérard, B., Chatterjee, K., &#38; Sznajder, N. (2015). Probabilistic opacity for Markov decision processes. <i> Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">https://doi.org/10.1016/j.ipl.2014.09.001</a>"},"publist_id":"5025","year":"2015","doi":"10.1016/j.ipl.2014.09.001","_id":"2034"},{"related_material":{"record":[{"relation":"part_of_dissertation","id":"1709","status":"public"},{"id":"2000","relation":"part_of_dissertation","status":"public"},{"id":"2247","relation":"part_of_dissertation","status":"public"},{"status":"public","id":"2816","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"2858","status":"public"},{"relation":"part_of_dissertation","id":"3157","status":"public"},{"relation":"part_of_dissertation","id":"3260","status":"public"}]},"degree_awarded":"PhD","date_updated":"2023-09-07T11:40:44Z","article_processing_charge":"No","year":"2015","title":"The subclonal evolution of cancer","date_created":"2018-12-11T11:51:48Z","publist_id":"5807","citation":{"ista":"Reiter J. 2015. The subclonal evolution of cancer. Institute of Science and Technology Austria.","mla":"Reiter, Johannes. <i>The Subclonal Evolution of Cancer</i>. Institute of Science and Technology Austria, 2015.","chicago":"Reiter, Johannes. “The Subclonal Evolution of Cancer.” Institute of Science and Technology Austria, 2015.","ama":"Reiter J. The subclonal evolution of cancer. 2015.","ieee":"J. Reiter, “The subclonal evolution of cancer,” Institute of Science and Technology Austria, 2015.","short":"J. Reiter, The Subclonal Evolution of Cancer, Institute of Science and Technology Austria, 2015.","apa":"Reiter, J. (2015). <i>The subclonal evolution of cancer</i>. Institute of Science and Technology Austria."},"language":[{"iso":"eng"}],"_id":"1400","publication_identifier":{"issn":["2663-337X"]},"month":"04","day":"01","oa_version":"None","abstract":[{"text":"Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease.","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","author":[{"orcid":"0000-0002-0170-7353","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter","full_name":"Reiter, Johannes","first_name":"Johannes"}],"alternative_title":["ISTA Thesis"],"publisher":"Institute of Science and Technology Austria","type":"dissertation","date_published":"2015-04-01T00:00:00Z","supervisor":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"}],"status":"public","page":"183","department":[{"_id":"KrCh"}]},{"ddc":["004"],"month":"01","publication_identifier":{"issn":["2664-1690"]},"oa_version":"Published Version","day":"12","file":[{"file_id":"5533","checksum":"e4869a584567c506349abda9c8ec7db3","file_name":"IST-2015-318-v1+1_main.pdf","date_created":"2018-12-12T11:54:11Z","date_updated":"2020-07-14T12:46:52Z","creator":"system","file_size":689863,"relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"abstract":[{"text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.  \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.\r\nOur problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.\r\nFinally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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"},{"first_name":"Zuzana","full_name":"Komarkova, Zuzana","last_name":"Komarkova"},{"first_name":"Jan","full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","orcid":"0000-0002-8122-2881"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"date_published":"2015-01-12T00:00:00Z","status":"public","type":"technical_report","page":"41","department":[{"_id":"KrCh"}],"has_accepted_license":"1","related_material":{"record":[{"status":"public","id":"1657","relation":"later_version"},{"id":"466","relation":"later_version","status":"public"},{"relation":"later_version","id":"5435","status":"public"}]},"date_updated":"2023-02-23T12:26:16Z","pubrep_id":"318","oa":1,"year":"2015","date_created":"2018-12-12T11:39:17Z","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","citation":{"apa":"Chatterjee, K., Komarkova, Z., &#38; Kretinsky, J. (2015). <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">https://doi.org/10.15479/AT:IST-2015-318-v1-1</a>","ama":"Chatterjee K, Komarkova Z, Kretinsky J. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria, 2015.","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">https://doi.org/10.15479/AT:IST-2015-318-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>."},"doi":"10.15479/AT:IST-2015-318-v1-1","file_date_updated":"2020-07-14T12:46:52Z","_id":"5429","language":[{"iso":"eng"}]},{"_id":"5430","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:52Z","doi":"10.15479/AT:IST-2015-319-v1-1","title":"Faster algorithms for quantitative verification in constant treewidth graphs","date_created":"2018-12-12T11:39:17Z","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">10.15479/AT:IST-2015-319-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">10.15479/AT:IST-2015-319-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015."},"year":"2015","date_updated":"2023-02-23T12:26:22Z","pubrep_id":"319","oa":1,"has_accepted_license":"1","related_material":{"record":[{"id":"1607","relation":"later_version","status":"public"},{"id":"5437","relation":"later_version","status":"public"}]},"page":"31","department":[{"_id":"KrCh"}],"status":"public","date_published":"2015-02-10T00:00:00Z","type":"technical_report","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"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","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen"},{"last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks."}],"file":[{"checksum":"62c6ea01e342553dcafb88a070fb1ad5","file_id":"5482","file_name":"IST-2015-319-v1+1_long.pdf","date_updated":"2020-07-14T12:46:52Z","date_created":"2018-12-12T11:53:21Z","creator":"system","file_size":1089651,"content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"oa_version":"Published Version","day":"10","publication_identifier":{"issn":["2664-1690"]},"month":"02","ddc":["000"]},{"doi":"10.15479/AT:IST-2015-322-v1-1","file_date_updated":"2020-07-14T12:46:53Z","language":[{"iso":"eng"}],"_id":"5431","has_accepted_license":"1","pubrep_id":"322","date_updated":"2021-01-12T08:02:13Z","oa":1,"year":"2015","title":"The patience of concurrent stochastic games with safety and reachability objectives","date_created":"2018-12-12T11:39:17Z","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Hansen, K. (2015). <i>The patience of concurrent stochastic games with safety and reachability objectives</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">https://doi.org/10.15479/AT:IST-2015-322-v1-1</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">https://doi.org/10.15479/AT:IST-2015-322-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">10.15479/AT:IST-2015-322-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.","short":"K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, <i>The patience of concurrent stochastic games with safety and reachability objectives</i>. IST Austria, 2015.","ama":"Chatterjee K, Ibsen-Jensen R, Hansen K. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">10.15479/AT:IST-2015-322-v1-1</a>"},"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","type":"technical_report","status":"public","date_published":"2015-02-19T00:00:00Z","department":[{"_id":"KrCh"}],"page":"25","ddc":["005","519"],"publication_identifier":{"issn":["2664-1690"]},"month":"02","day":"19","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.\r\n\r\n Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_created":"2018-12-12T11:53:31Z","date_updated":"2020-07-14T12:46:53Z","checksum":"bfb858262c30445b8e472c40069178a2","file_id":"5491","file_name":"IST-2015-322-v1+1_safetygames.pdf","content_type":"application/pdf","relation":"main_file","file_size":661015,"access_level":"open_access","creator":"system"}],"publication_status":"published","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus"},{"first_name":"Kristoffer","full_name":"Hansen, Kristoffer","last_name":"Hansen"}]},{"file":[{"file_id":"5519","checksum":"546c1b291d545e7b24aaaf4199dac671","file_name":"IST-2015-323-v1+1_main.pdf","date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:53:57Z","creator":"system","relation":"main_file","file_size":576347,"content_type":"application/pdf","access_level":"open_access"}],"user_id":"2DF688A6-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. \r\nThe vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. 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. \r\nOur main results are:\r\n(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).\r\n(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.\r\n"}],"oa_version":"Published Version","day":"19","publication_identifier":{"issn":["2664-1690"]},"month":"02","ddc":["005","576"],"publication_status":"published","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","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"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"department":[{"_id":"KrCh"}],"page":"29","status":"public","type":"technical_report","date_published":"2015-02-19T00:00:00Z","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"related_material":{"record":[{"id":"5421","relation":"earlier_version","status":"public"},{"id":"5440","relation":"later_version","status":"public"}]},"has_accepted_license":"1","date_created":"2018-12-12T11:39:18Z","citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">10.15479/AT:IST-2015-323-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">10.15479/AT:IST-2015-323-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity of evolutionary games on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a>"},"title":"The complexity of evolutionary games on graphs","year":"2015","pubrep_id":"323","oa":1,"date_updated":"2023-02-23T12:26:33Z","doi":"10.15479/AT:IST-2015-323-v1-1","language":[{"iso":"eng"}],"_id":"5432","file_date_updated":"2020-07-14T12:46:53Z"},{"publication_status":"published","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Zuzana","full_name":"Komarkova, Zuzana","last_name":"Komarkova"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","first_name":"Jan","full_name":"Kretinsky, Jan"}],"oa_version":"Published Version","day":"23","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.  \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP.\r\nWe also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.","lang":"eng"}],"file":[{"checksum":"75284adec80baabdfe71ff9ebbc27445","file_id":"5525","file_name":"IST-2015-318-v2+1_main.pdf","date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:54:03Z","creator":"system","file_size":717630,"content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"ddc":["004"],"month":"02","publication_identifier":{"issn":["2664-1690"]},"page":"51","department":[{"_id":"KrCh"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"status":"public","date_published":"2015-02-23T00:00:00Z","type":"technical_report","date_created":"2018-12-12T11:39:19Z","citation":{"apa":"Chatterjee, K., Komarkova, Z., &#38; Kretinsky, J. (2015). <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">https://doi.org/10.15479/AT:IST-2015-318-v2-1</a>","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria, 2015.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">10.15479/AT:IST-2015-318-v2-1</a>","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">10.15479/AT:IST-2015-318-v2-1</a>.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 51p.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">https://doi.org/10.15479/AT:IST-2015-318-v2-1</a>."},"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","date_updated":"2023-02-23T12:26:00Z","pubrep_id":"327","oa":1,"year":"2015","related_material":{"record":[{"relation":"later_version","id":"1657","status":"public"},{"relation":"later_version","id":"466","status":"public"},{"status":"public","id":"5429","relation":"earlier_version"}]},"has_accepted_license":"1","file_date_updated":"2020-07-14T12:46:53Z","language":[{"iso":"eng"}],"_id":"5435","doi":"10.15479/AT:IST-2015-318-v2-1"},{"date_published":"2015-04-24T00:00:00Z","status":"public","type":"technical_report","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"page":"29","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","first_name":"Jan"}],"publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"month":"04","ddc":["000"],"abstract":[{"text":"Recently there has been a significant effort to handle 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, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.\r\nIn nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.","lang":"eng"}],"file":[{"creator":"system","content_type":"application/pdf","relation":"main_file","file_size":569991,"access_level":"open_access","file_name":"IST-2015-170-v2+2_report.pdf","checksum":"3c402f47d3669c28d04d1af405a08e3f","file_id":"5541","date_updated":"2020-07-14T12:46:54Z","date_created":"2018-12-12T11:54:19Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"24","_id":"5436","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:54Z","doi":"10.15479/AT:IST-2015-170-v2-2","year":"2015","date_updated":"2023-02-23T12:25:21Z","oa":1,"pubrep_id":"331","date_created":"2018-12-12T11:39:19Z","title":"Nested weighted automata","citation":{"apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2015). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">https://doi.org/10.15479/AT:IST-2015-170-v2-2</a>","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">10.15479/AT:IST-2015-170-v2-2</a>","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2015.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">https://doi.org/10.15479/AT:IST-2015-170-v2-2</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">10.15479/AT:IST-2015-170-v2-2</a>.","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p."},"related_material":{"record":[{"status":"public","relation":"later_version","id":"1656"},{"relation":"later_version","id":"467","status":"public"},{"status":"public","relation":"earlier_version","id":"5415"}]},"has_accepted_license":"1"}]