[{"author":[{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"},{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec"},{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"file_date_updated":"2020-07-14T12:46:59Z","date_created":"2018-12-12T11:39:25Z","publication_identifier":{"issn":["2664-1690"]},"oa":1,"ddc":["000"],"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2017-749-v3-1","publication_status":"published","pubrep_id":"755","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publisher":"IST Austria","title":"Arbitrarily strong amplifiers of natural selection","type":"technical_report","citation":{"ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria; 2016. doi:10.15479/AT:IST-2017-749-v3-1","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Arbitrarily strong amplifiers of natural selection, IST Austria, 34p.","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria, 2016. https://doi.org/10.15479/AT:IST-2017-749-v3-1.","mla":"Pavlogiannis, Andreas, et al. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria, 2016, doi:10.15479/AT:IST-2017-749-v3-1.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, Arbitrarily strong amplifiers of natural selection. IST Austria, 2016.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2016). Arbitrarily strong amplifiers of natural selection. IST Austria. https://doi.org/10.15479/AT:IST-2017-749-v3-1","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016."},"alternative_title":["IST Austria Technical Report"],"month":"12","date_published":"2016-12-30T00:00:00Z","_id":"5453","department":[{"_id":"KrCh"}],"page":"34","has_accepted_license":"1","file":[{"file_name":"IST-2017-749-v3+1_main.pdf","date_created":"2018-12-12T11:53:13Z","content_type":"application/pdf","file_id":"5474","creator":"system","checksum":"83b0313dab3bff4bdb6ac38695026fda","date_updated":"2020-07-14T12:46:59Z","access_level":"open_access","relation":"main_file","file_size":1015647}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5452"}]},"day":"30","date_updated":"2023-02-23T12:27:07Z","year":"2016"},{"doi":"10.15479/AT:IST-2016-728-v1-1","language":[{"iso":"eng"}],"ddc":["000"],"oa":1,"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:24Z","file_date_updated":"2020-07-14T12:46:59Z","author":[{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis"},{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"citation":{"short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Strong Amplifiers of Natural Selection, IST Austria, 2016.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2016). Strong amplifiers of natural selection. IST Austria. https://doi.org/10.15479/AT:IST-2016-728-v1-1","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, Strong amplifiers of natural selection. IST Austria, 2016.","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. Strong Amplifiers of Natural Selection. IST Austria, 2016. https://doi.org/10.15479/AT:IST-2016-728-v1-1.","mla":"Pavlogiannis, Andreas, et al. Strong Amplifiers of Natural Selection. IST Austria, 2016, doi:10.15479/AT:IST-2016-728-v1-1.","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Strong Amplifiers of Natural Selection. IST Austria; 2016. doi:10.15479/AT:IST-2016-728-v1-1","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Strong amplifiers of natural selection, IST Austria, 34p."},"title":"Strong amplifiers of natural selection","type":"technical_report","status":"public","publisher":"IST Austria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","publication_status":"published","pubrep_id":"728","file":[{"file_id":"5465","content_type":"application/pdf","date_created":"2018-12-12T11:53:04Z","file_name":"IST-2016-728-v1+1_main.pdf","access_level":"open_access","relation":"main_file","file_size":1014732,"checksum":"7b8bb17c322c0556acba6ac169fa71c1","creator":"system","date_updated":"2020-07-14T12:46:59Z"}],"page":"34","has_accepted_license":"1","department":[{"_id":"KrCh"}],"_id":"5451","date_published":"2016-12-30T00:00:00Z","month":"12","alternative_title":["IST Austria Technical Report"],"year":"2016","date_updated":"2023-02-23T12:27:05Z","day":"30"},{"related_material":{"record":[{"status":"public","relation":"later_version","id":"10417"},{"status":"public","id":"5456","relation":"later_version"}]},"day":"15","date_updated":"2023-02-23T12:27:16Z","year":"2016","external_id":{"arxiv":["1610.01188"]},"alternative_title":["IST Austria Technical Report"],"date_published":"2016-07-15T00:00:00Z","month":"07","_id":"5448","file":[{"file_size":538881,"relation":"main_file","access_level":"open_access","date_updated":"2020-07-14T12:46:58Z","creator":"system","checksum":"1d69252d66bcdf782615ddfb911d2957","file_name":"IST-2016-620-v1+1_main.pdf","date_created":"2018-12-12T11:53:45Z","file_id":"5506","content_type":"application/pdf"},{"file_name":"authornames.txt","date_created":"2019-05-10T13:30:40Z","content_type":"text/plain","file_id":"6405","relation":"main_file","access_level":"closed","file_size":121,"creator":"dernst","checksum":"deabb0eb8f237cae4f9542b28b0b6eb2","date_updated":"2020-07-14T12:46:58Z"}],"page":"20","has_accepted_license":"1","abstract":[{"lang":"eng","text":"We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class.\r\nWe introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence.\r\n1. For acyclic architectures, our algorithm is guaranteed to explore exactly one representative trace from each observation class, while spending polynomial time per class. Hence, our algorithm is optimal wrt the observation equivalence, and in several cases explores exponentially fewer traces than any enumerative method based on the Mazurkiewicz equivalence.\r\n2. For cyclic architectures, we consider an equivalence between traces which is finer than the observation equivalence; but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence. \r\nFinally, we perform a basic experimental comparison between the existing Mazurkiewicz-based DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show a significant reduction in both running time and the number of explored equivalence classes."}],"pubrep_id":"620","publication_status":"published","oa_version":"Published Version","type":"technical_report","title":"Data-centric dynamic partial order reduction","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","citation":{"ama":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Data-Centric Dynamic Partial Order Reduction. IST Austria; 2016.","ista":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2016. Data-centric dynamic partial order reduction, IST Austria, 20p.","mla":"Anonymous, 1, et al. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2016.","chicago":"Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Data-Centric Dynamic Partial Order Reduction. IST Austria, 2016.","ieee":"1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Data-centric dynamic partial order reduction. IST Austria, 2016.","short":"1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2016.","apa":"Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2016). Data-centric dynamic partial order reduction. IST Austria."},"file_date_updated":"2020-07-14T12:46:58Z","author":[{"last_name":"Anonymous","first_name":"1","full_name":"Anonymous, 1"},{"last_name":"Anonymous","first_name":"2","full_name":"Anonymous, 2"},{"last_name":"Anonymous","first_name":"3","full_name":"Anonymous, 3"},{"full_name":"Anonymous, 4","last_name":"Anonymous","first_name":"4"}],"date_created":"2018-12-12T11:39:23Z","language":[{"iso":"eng"}],"ddc":["000"],"oa":1,"publication_identifier":{"issn":["2664-1690"]}},{"has_accepted_license":"1","file":[{"creator":"system","checksum":"58e895f26c82f560c0f0989bf8b08599","date_updated":"2020-07-14T12:46:59Z","relation":"main_file","access_level":"open_access","file_size":811558,"file_name":"IST-2017-728-v2+1_main.pdf","date_created":"2018-12-12T11:52:59Z","content_type":"application/pdf","file_id":"5460"}],"page":"32","article_processing_charge":"No","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}],"ddc":["000"],"oa":1,"date_created":"2018-12-12T11:39:25Z","ec_funded":1,"title":"Arbitrarily strong amplifiers of natural selection","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","oa_version":"Published Version","department":[{"_id":"KrCh"}],"_id":"5452","date_published":"2016-12-30T00:00:00Z","month":"12","alternative_title":["IST Austria Technical Report"],"year":"2016","date_updated":"2024-02-21T13:48:42Z","day":"30","related_material":{"record":[{"status":"public","relation":"later_version","id":"5453"},{"relation":"popular_science","id":"5559","status":"public"}]},"doi":"10.15479/AT:IST-2017-728-v2-1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:59Z","author":[{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"},{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"citation":{"ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, Arbitrarily strong amplifiers of natural selection. IST Austria, 2016.","short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong Amplifiers of Natural Selection, IST Austria, 2016.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2016). Arbitrarily strong amplifiers of natural selection. IST Austria. https://doi.org/10.15479/AT:IST-2017-728-v2-1","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria; 2016. doi:10.15479/AT:IST-2017-728-v2-1","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Arbitrarily strong amplifiers of natural selection, IST Austria, 32p.","mla":"Pavlogiannis, Andreas, et al. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria, 2016, doi:10.15479/AT:IST-2017-728-v2-1.","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria, 2016. https://doi.org/10.15479/AT:IST-2017-728-v2-1."},"type":"technical_report","status":"public","publication_status":"published","pubrep_id":"750"},{"_id":"5431","department":[{"_id":"KrCh"}],"file":[{"file_name":"IST-2015-322-v1+1_safetygames.pdf","date_created":"2018-12-12T11:53:31Z","content_type":"application/pdf","file_id":"5491","creator":"system","checksum":"bfb858262c30445b8e472c40069178a2","date_updated":"2020-07-14T12:46:53Z","access_level":"open_access","relation":"main_file","file_size":661015}],"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."}],"has_accepted_license":"1","page":"25","alternative_title":["IST Austria Technical Report"],"month":"02","date_published":"2015-02-19T00:00:00Z","date_updated":"2021-01-12T08:02:13Z","year":"2015","day":"19","oa":1,"publication_identifier":{"issn":["2664-1690"]},"ddc":["005","519"],"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2015-322-v1-1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen"},{"last_name":"Hansen","first_name":"Kristoffer","full_name":"Hansen, Kristoffer"}],"file_date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:39:17Z","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.","ama":"Chatterjee K, Ibsen-Jensen R, Hansen K. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria; 2015. doi:10.15479/AT:IST-2015-322-v1-1","mla":"Chatterjee, Krishnendu, et al. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria, 2015, doi:10.15479/AT:IST-2015-322-v1-1.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-322-v1-1.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, The patience of concurrent stochastic games with safety and reachability objectives. IST Austria, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Hansen, K. (2015). The patience of concurrent stochastic games with safety and reachability objectives. IST Austria. https://doi.org/10.15479/AT:IST-2015-322-v1-1"},"oa_version":"Published Version","pubrep_id":"322","publication_status":"published","status":"public","publisher":"IST Austria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"The patience of concurrent stochastic games with safety and reachability objectives","type":"technical_report"},{"ddc":["000"],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"oa":1,"file_date_updated":"2020-07-14T12:46:53Z","author":[{"first_name":"1","last_name":"Anonymous","full_name":"Anonymous, 1"},{"full_name":"Anonymous, 2","last_name":"Anonymous","first_name":"2"}],"date_created":"2018-12-12T11:39:18Z","citation":{"ieee":"1 Anonymous and 2 Anonymous, Optimal cost indefinite-horizon reachability in goal DEC-POMDPs. IST Austria, 2015.","short":"1 Anonymous, 2 Anonymous, Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs, IST Austria, 2015.","apa":"Anonymous, 1, & Anonymous, 2. (2015). Optimal cost indefinite-horizon reachability in goal DEC-POMDPs. IST Austria.","ista":"Anonymous 1, Anonymous 2. 2015. Optimal cost indefinite-horizon reachability in goal DEC-POMDPs, IST Austria, 16p.","ama":"Anonymous 1, Anonymous 2. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria; 2015.","mla":"Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria, 2015.","chicago":"Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria, 2015."},"oa_version":"Published Version","publication_status":"published","pubrep_id":"326","title":"Optimal cost indefinite-horizon reachability in goal DEC-POMDPs","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publisher":"IST Austria","_id":"5434","file":[{"access_level":"open_access","relation":"main_file","file_size":378162,"checksum":"8542fd0b10aed7811cd41077b8ccb632","creator":"system","date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:53:14Z","file_name":"IST-2015-326-v1+1_main.pdf","file_id":"5475","content_type":"application/pdf"},{"date_updated":"2020-07-14T12:46:53Z","checksum":"84c31c537bdaf7a91909f18d25d640ab","creator":"dernst","file_size":64,"access_level":"closed","relation":"main_file","content_type":"text/plain","file_id":"6317","file_name":"IST-2015-326-v1+2_authors.txt","date_created":"2019-04-16T13:00:33Z"}],"abstract":[{"lang":"eng","text":"DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results."}],"page":"16","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"date_published":"2015-02-19T00:00:00Z","month":"02","date_updated":"2020-07-14T23:04:59Z","year":"2015","day":"19"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","status":"public","type":"technical_report","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","pubrep_id":"318","oa_version":"Published Version","publication_status":"published","citation":{"chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v1-1.","mla":"Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v1-1.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v1-1","apa":"Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2015-318-v1-1","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria, 2015."},"date_created":"2018-12-12T11:39:17Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Zuzana","last_name":"Komarkova","full_name":"Komarkova, Zuzana"},{"last_name":"Kretinsky","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan"}],"file_date_updated":"2020-07-14T12:46:52Z","doi":"10.15479/AT:IST-2015-318-v1-1","publication_identifier":{"issn":["2664-1690"]},"oa":1,"ddc":["004"],"language":[{"iso":"eng"}],"day":"12","related_material":{"record":[{"id":"1657","relation":"later_version","status":"public"},{"status":"public","relation":"later_version","id":"466"},{"status":"public","id":"5435","relation":"later_version"}]},"year":"2015","date_updated":"2023-02-23T12:26:16Z","month":"01","date_published":"2015-01-12T00:00:00Z","alternative_title":["IST Austria Technical Report"],"page":"41","has_accepted_license":"1","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"}],"file":[{"file_size":689863,"access_level":"open_access","relation":"main_file","date_updated":"2020-07-14T12:46:52Z","creator":"system","checksum":"e4869a584567c506349abda9c8ec7db3","file_id":"5533","content_type":"application/pdf","date_created":"2018-12-12T11:54:11Z","file_name":"IST-2015-318-v1+1_main.pdf"}],"_id":"5429","department":[{"_id":"KrCh"}]},{"citation":{"ama":"Chatterjee K, Komarkova Z, Kretinsky J. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v2-1","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 51p.","mla":"Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v2-1.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v2-1.","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, Unifying two views on multiple mean-payoff objectives in Markov decision processes. 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.","apa":"Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2015-318-v2-1"},"oa_version":"Published Version","publication_status":"published","pubrep_id":"327","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","status":"public","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","type":"technical_report","publication_identifier":{"issn":["2664-1690"]},"oa":1,"ddc":["004"],"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2015-318-v2-1","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Komarkova","first_name":"Zuzana","full_name":"Komarkova, Zuzana"},{"last_name":"Kretinsky","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan"}],"file_date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:39:19Z","date_updated":"2023-02-23T12:26:00Z","year":"2015","related_material":{"record":[{"status":"public","id":"1657","relation":"later_version"},{"id":"466","relation":"later_version","status":"public"},{"relation":"earlier_version","id":"5429","status":"public"}]},"day":"23","_id":"5435","department":[{"_id":"KrCh"}],"file":[{"file_id":"5525","content_type":"application/pdf","file_name":"IST-2015-318-v2+1_main.pdf","date_created":"2018-12-12T11:54:03Z","creator":"system","checksum":"75284adec80baabdfe71ff9ebbc27445","date_updated":"2020-07-14T12:46:53Z","relation":"main_file","access_level":"open_access","file_size":717630}],"abstract":[{"lang":"eng","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."}],"page":"51","has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"month":"02","date_published":"2015-02-23T00:00:00Z"},{"file":[{"date_updated":"2020-07-14T12:46:54Z","creator":"system","checksum":"3c402f47d3669c28d04d1af405a08e3f","file_size":569991,"relation":"main_file","access_level":"open_access","file_id":"5541","content_type":"application/pdf","date_created":"2018-12-12T11:54:19Z","file_name":"IST-2015-170-v2+2_report.pdf"}],"has_accepted_license":"1","abstract":[{"lang":"eng","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."}],"page":"29","_id":"5436","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"month":"04","date_published":"2015-04-24T00:00:00Z","alternative_title":["IST Austria Technical Report"],"year":"2015","date_updated":"2023-02-23T12:25:21Z","day":"24","related_material":{"record":[{"relation":"later_version","id":"1656","status":"public"},{"id":"467","relation":"later_version","status":"public"},{"id":"5415","relation":"earlier_version","status":"public"}]},"doi":"10.15479/AT:IST-2015-170-v2-2","publication_identifier":{"issn":["2664-1690"]},"oa":1,"language":[{"iso":"eng"}],"ddc":["000"],"date_created":"2018-12-12T11:39:19Z","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","full_name":"Otop, Jan"}],"file_date_updated":"2020-07-14T12:46:54Z","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, Nested weighted automata. IST Austria, 2015.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). Nested weighted automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-170-v2-2","ama":"Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-170-v2-2","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p.","mla":"Chatterjee, Krishnendu, et al. Nested Weighted Automata. IST Austria, 2015, doi:10.15479/AT:IST-2015-170-v2-2.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. Nested Weighted Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-170-v2-2."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","status":"public","type":"technical_report","title":"Nested weighted automata","publication_status":"published","oa_version":"Published Version","pubrep_id":"331"},{"doi":"10.15479/AT:IST-2015-330-v2-1","oa":1,"publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"language":[{"iso":"eng"}],"date_created":"2018-12-12T11:39:19Z","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"}],"file_date_updated":"2020-07-14T12:46:54Z","citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-330-v2-1","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-330-v2-1.","mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-330-v2-1.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-330-v2-1","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","status":"public","type":"technical_report","title":"Faster algorithms for quantitative verification in constant treewidth graphs","publication_status":"published","pubrep_id":"333","oa_version":"Published Version","page":"27","has_accepted_license":"1","file":[{"file_name":"IST-2015-330-v2+1_main.pdf","date_created":"2018-12-12T11:53:12Z","content_type":"application/pdf","file_id":"5473","creator":"system","checksum":"f5917c20f84018b362d385c000a2e123","date_updated":"2020-07-14T12:46:54Z","access_level":"open_access","relation":"main_file","file_size":1072137}],"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. \r\nThe 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.\r\nOur main theoretical results are as follows.\r\nFirst, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ 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 \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when the output is $\\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$ and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. "}],"_id":"5437","department":[{"_id":"KrCh"}],"month":"04","date_published":"2015-04-27T00:00:00Z","alternative_title":["IST Austria Technical Report"],"year":"2015","date_updated":"2023-02-23T12:26:05Z","day":"27","related_material":{"record":[{"id":"1607","relation":"later_version","status":"public"},{"relation":"earlier_version","id":"5430","status":"public"}]}}]