[{"_id":"523","year":"2015","volume":242,"page":"25 - 52","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","citation":{"ieee":"K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 25–52, 2015.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>.","apa":"Chatterjee, K., Doyen, L., Randour, M., &#38; Raskin, J. (2015). Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>","ama":"Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. 2015;242(6):25-52. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>","short":"K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.","mla":"Chatterjee, Krishnendu, et al. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 25–52, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>.","ista":"Chatterjee K, Doyen L, Randour M, Raskin J. 2015. Looking at mean-payoff and total-payoff through windows. Information and Computation. 242(6), 25–52."},"oa":1,"status":"public","issue":"6","date_created":"2018-12-11T11:46:57Z","ec_funded":1,"oa_version":"Preprint","publist_id":"7296","publication":"Information and Computation","department":[{"_id":"KrCh"}],"title":"Looking at mean-payoff and total-payoff through windows","publisher":"Elsevier","abstract":[{"lang":"eng","text":"We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window."}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1302.4248"}],"intvolume":"       242","publication_status":"published","month":"03","language":[{"iso":"eng"}],"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"day":"24","scopus_import":1,"quality_controlled":"1","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"},{"last_name":"Randour","first_name":"Mickael","full_name":"Randour, Mickael"},{"full_name":"Raskin, Jean","last_name":"Raskin","first_name":"Jean"}],"date_published":"2015-03-24T00:00:00Z","doi":"10.1016/j.ic.2015.03.010","related_material":{"record":[{"id":"2279","relation":"earlier_version","status":"public"}]},"date_updated":"2023-02-23T10:36:02Z"},{"year":"2015","_id":"524","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","volume":242,"page":"2 - 24","citation":{"apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “Qualitative analysis of concurrent mean payoff games,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 2–24, 2015.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 2–24, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.","short":"K. Chatterjee, R. Ibsen-Jensen, Information and Computation 242 (2015) 2–24.","ama":"Chatterjee K, Ibsen-Jensen R. Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. 2015;242(6):2-24. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>"},"issue":"6","external_id":{"arxiv":["1409.5306"]},"status":"public","oa":1,"publist_id":"7295","date_created":"2018-12-11T11:46:57Z","oa_version":"Preprint","publisher":"Elsevier","publication":"Information and Computation","department":[{"_id":"KrCh"}],"title":"Qualitative analysis of concurrent mean payoff games","abstract":[{"lang":"eng","text":"We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time."}],"arxiv":1,"publication_status":"published","main_file_link":[{"url":"https://arxiv.org/abs/1409.5306","open_access":"1"}],"intvolume":"       242","month":"10","language":[{"iso":"eng"}],"day":"11","quality_controlled":"1","scopus_import":1,"date_updated":"2023-02-23T12:24:45Z","related_material":{"record":[{"id":"5403","status":"public","relation":"earlier_version"}]},"doi":"10.1016/j.ic.2015.03.009","date_published":"2015-10-11T00:00:00Z","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"}]},{"page":"41","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","_id":"5429","file":[{"date_updated":"2020-07-14T12:46:52Z","file_id":"5533","file_size":689863,"file_name":"IST-2015-318-v1+1_main.pdf","checksum":"e4869a584567c506349abda9c8ec7db3","relation":"main_file","creator":"system","access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T11:54:11Z"}],"has_accepted_license":"1","year":"2015","publication_status":"published","oa":1,"status":"public","ddc":["004"],"day":"12","citation":{"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>","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-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","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.","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>.","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>"},"month":"01","publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:52Z","publisher":"IST Austria","date_created":"2018-12-12T11:39:17Z","oa_version":"Published Version","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Komarkova, Zuzana","last_name":"Komarkova","first_name":"Zuzana"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","first_name":"Jan"}],"date_published":"2015-01-12T00:00:00Z","pubrep_id":"318","related_material":{"record":[{"status":"public","relation":"later_version","id":"1657"},{"status":"public","relation":"later_version","id":"466"},{"id":"5435","relation":"later_version","status":"public"}]},"date_updated":"2023-02-23T12:26:16Z","doi":"10.15479/AT:IST-2015-318-v1-1","alternative_title":["IST Austria Technical Report"],"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"}]},{"title":"Faster algorithms for quantitative verification in constant treewidth graphs","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:52Z","publisher":"IST Austria","date_created":"2018-12-12T11:39:17Z","oa_version":"Published Version","date_published":"2015-02-10T00:00:00Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","first_name":"Andreas"}],"pubrep_id":"319","date_updated":"2023-02-23T12:26:22Z","related_material":{"record":[{"id":"1607","relation":"later_version","status":"public"},{"relation":"later_version","status":"public","id":"5437"}]},"doi":"10.15479/AT:IST-2015-319-v1-1","alternative_title":["IST Austria Technical Report"],"abstract":[{"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.","lang":"eng"}],"page":"31","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","_id":"5430","file":[{"content_type":"application/pdf","date_created":"2018-12-12T11:53:21Z","relation":"main_file","creator":"system","access_level":"open_access","file_size":1089651,"file_name":"IST-2015-319-v1+1_long.pdf","checksum":"62c6ea01e342553dcafb88a070fb1ad5","file_id":"5482","date_updated":"2020-07-14T12:46:52Z"}],"has_accepted_license":"1","year":"2015","publication_status":"published","oa":1,"status":"public","ddc":["000"],"day":"10","citation":{"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>","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","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>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015.","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>.","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>"},"month":"02","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]}},{"_id":"5431","file":[{"file_id":"5491","date_updated":"2020-07-14T12:46:53Z","checksum":"bfb858262c30445b8e472c40069178a2","file_name":"IST-2015-322-v1+1_safetygames.pdf","file_size":661015,"access_level":"open_access","creator":"system","relation":"main_file","date_created":"2018-12-12T11:53:31Z","content_type":"application/pdf"}],"year":"2015","has_accepted_license":"1","publication_status":"published","page":"25","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","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>","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.","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>.","ista":"Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.","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>.","short":"K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, 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>"},"month":"02","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"status":"public","oa":1,"ddc":["005","519"],"day":"19","date_created":"2018-12-12T11:39:17Z","oa_version":"Published Version","department":[{"_id":"KrCh"}],"title":"The patience of concurrent stochastic games with safety and reachability objectives","file_date_updated":"2020-07-14T12:46:53Z","publisher":"IST Austria","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."}],"date_published":"2015-02-19T00:00:00Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"},{"last_name":"Hansen","first_name":"Kristoffer","full_name":"Hansen, Kristoffer"}],"pubrep_id":"322","doi":"10.15479/AT:IST-2015-322-v1-1","date_updated":"2021-01-12T08:02:13Z","alternative_title":["IST Austria Technical Report"]},{"file_date_updated":"2020-07-14T12:46:53Z","department":[{"_id":"KrCh"}],"title":"The complexity of evolutionary games on graphs","publisher":"IST Austria","date_created":"2018-12-12T11:39:18Z","oa_version":"Published Version","pubrep_id":"323","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"date_published":"2015-02-19T00:00:00Z","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:26:33Z","related_material":{"record":[{"id":"5421","status":"public","relation":"earlier_version"},{"id":"5440","relation":"later_version","status":"public"}]},"doi":"10.15479/AT:IST-2015-323-v1-1","abstract":[{"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","lang":"eng"}],"page":"29","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","_id":"5432","year":"2015","has_accepted_license":"1","file":[{"file_size":576347,"file_name":"IST-2015-323-v1+1_main.pdf","checksum":"546c1b291d545e7b24aaaf4199dac671","file_id":"5519","date_updated":"2020-07-14T12:46:53Z","content_type":"application/pdf","date_created":"2018-12-12T11:53:57Z","relation":"main_file","access_level":"open_access","creator":"system"}],"publication_status":"published","oa":1,"status":"public","ddc":["005","576"],"day":"19","citation":{"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>","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>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","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>.","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>"},"month":"02","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]}},{"publication_status":"published","year":"2015","has_accepted_license":"1","file":[{"file_size":717630,"checksum":"75284adec80baabdfe71ff9ebbc27445","file_name":"IST-2015-318-v2+1_main.pdf","file_id":"5525","date_updated":"2020-07-14T12:46:53Z","content_type":"application/pdf","date_created":"2018-12-12T11:54:03Z","relation":"main_file","access_level":"open_access","creator":"system"}],"_id":"5435","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"51","publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"month":"02","citation":{"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>","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 51p.","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>.","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>.","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.","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>"},"day":"23","ddc":["004"],"status":"public","oa":1,"oa_version":"Published Version","date_created":"2018-12-12T11:39:19Z","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:53Z","department":[{"_id":"KrCh"}],"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","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."}],"alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:26:00Z","doi":"10.15479/AT:IST-2015-318-v2-1","related_material":{"record":[{"status":"public","relation":"later_version","id":"1657"},{"id":"466","status":"public","relation":"later_version"},{"relation":"earlier_version","status":"public","id":"5429"}]},"pubrep_id":"327","date_published":"2015-02-23T00:00:00Z","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Komarkova","first_name":"Zuzana","full_name":"Komarkova, Zuzana"},{"first_name":"Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"}]},{"oa_version":"Published Version","date_created":"2018-12-12T11:39:19Z","file_date_updated":"2020-07-14T12:46:54Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Nested weighted automata","publisher":"IST Austria","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"}],"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop"}],"pubrep_id":"331","date_published":"2015-04-24T00:00:00Z","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:25:21Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"1656"},{"id":"467","status":"public","relation":"later_version"},{"id":"5415","status":"public","relation":"earlier_version"}]},"doi":"10.15479/AT:IST-2015-170-v2-2","_id":"5436","publication_status":"published","has_accepted_license":"1","year":"2015","file":[{"date_created":"2018-12-12T11:54:19Z","content_type":"application/pdf","creator":"system","access_level":"open_access","relation":"main_file","file_name":"IST-2015-170-v2+2_report.pdf","checksum":"3c402f47d3669c28d04d1af405a08e3f","file_size":569991,"file_id":"5541","date_updated":"2020-07-14T12:46:54Z"}],"page":"29","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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>","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>.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2015.","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.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","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>"},"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"month":"04","status":"public","oa":1,"day":"24","ddc":["000"]},{"citation":{"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-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.","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-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>","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-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-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-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-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."},"month":"04","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"status":"public","oa":1,"ddc":["000"],"day":"27","_id":"5437","year":"2015","has_accepted_license":"1","file":[{"access_level":"open_access","creator":"system","relation":"main_file","date_created":"2018-12-12T11:53:12Z","content_type":"application/pdf","date_updated":"2020-07-14T12:46:54Z","file_id":"5473","checksum":"f5917c20f84018b362d385c000a2e123","file_name":"IST-2015-330-v2+1_main.pdf","file_size":1072137}],"publication_status":"published","page":"27","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","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. "}],"author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722"}],"date_published":"2015-04-27T00:00:00Z","pubrep_id":"333","related_material":{"record":[{"id":"1607","relation":"later_version","status":"public"},{"id":"5430","status":"public","relation":"earlier_version"}]},"date_updated":"2023-02-23T12:26:05Z","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2015-330-v2-1","date_created":"2018-12-12T11:39:19Z","oa_version":"Published Version","file_date_updated":"2020-07-14T12:46:54Z","department":[{"_id":"KrCh"}],"title":"Faster algorithms for quantitative verification in constant treewidth graphs","publisher":"IST Austria"},{"date_published":"2015-05-05T00:00:00Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"pubrep_id":"334","alternative_title":["IST Austria Technical Report"],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1610"},{"id":"465","status":"public","relation":"later_version"}]},"date_updated":"2023-02-23T12:20:08Z","doi":"10.15479/AT:IST-2015-334-v1-1","abstract":[{"text":"The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.\r\nThe problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. ","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:55Z","department":[{"_id":"KrCh"}],"title":"Edit distance for pushdown automata","publisher":"IST Austria","date_created":"2018-12-12T11:39:20Z","oa_version":"Published Version","status":"public","oa":1,"ddc":["004"],"day":"05","citation":{"ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. <i>Edit Distance for Pushdown Automata</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>.","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, <i>Edit distance for pushdown automata</i>. IST Austria, 2015.","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., &#38; Otop, J. (2015). <i>Edit distance for pushdown automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>"},"month":"05","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"page":"15","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","_id":"5438","file":[{"relation":"main_file","access_level":"open_access","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:53:56Z","date_updated":"2020-07-14T12:46:55Z","file_id":"5518","file_size":422573,"checksum":"8a5f2d77560e552af87eb1982437a43b","file_name":"IST-2015-334-v1+1_report.pdf"}],"has_accepted_license":"1","year":"2015","publication_status":"published"},{"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5421"},{"relation":"earlier_version","status":"public","id":"5432"}]},"doi":"10.15479/AT:IST-2015-323-v2-2","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:26:10Z","pubrep_id":"338","date_published":"2015-06-16T00:00:00Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"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 for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive."}],"publisher":"IST Austria","title":"The complexity of evolutionary games on graphs","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:56Z","date_created":"2018-12-12T11:39:21Z","oa_version":"Published Version","ddc":["005","576"],"day":"16","oa":1,"status":"public","month":"06","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"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-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p.","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-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","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-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015.","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-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","page":"18","has_accepted_license":"1","file":[{"relation":"main_file","access_level":"open_access","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:53:23Z","date_updated":"2020-07-14T12:46:56Z","file_id":"5484","file_size":466161,"file_name":"IST-2015-323-v2+2_main.pdf","checksum":"66aace7d367032af97c15e35c9be9636"}],"year":"2015","publication_status":"published","_id":"5440"},{"date_published":"2015-07-11T00:00:00Z","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"},{"first_name":"Amir","last_name":"Goharshady","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas"}],"pubrep_id":"340","date_updated":"2023-09-19T14:36:19Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"1437"},{"relation":"earlier_version","status":"public","id":"5442"},{"id":"6009","status":"public","relation":"later_version"}]},"doi":"10.15479/AT:IST-2015-340-v1-1","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.","lang":"eng"}],"title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","file_date_updated":"2020-07-14T12:46:56Z","department":[{"_id":"KrCh"}],"publisher":"IST Austria","date_created":"2018-12-12T11:39:21Z","oa_version":"Published Version","oa":1,"status":"public","ddc":["000"],"day":"11","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.","ista":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 24p.","ama":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>","apa":"Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., &#38; Pavlogiannis, A. (2015). <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>."},"month":"07","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"page":"24","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","_id":"5441","year":"2015","file":[{"file_id":"5531","date_updated":"2020-07-14T12:46:56Z","file_size":861396,"file_name":"IST-2015-340-v1+1_main.pdf","checksum":"df383dc62c94d7b2ea639aba088a76c6","relation":"main_file","access_level":"open_access","creator":"system","content_type":"application/pdf","date_created":"2018-12-12T11:54:09Z"}],"has_accepted_license":"1","publication_status":"published"},{"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>.","ista":"Chatterjee K, Chmelik M, Davies J. 2015. A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs, IST Austria, 23p.","short":"K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015.","ama":"Chatterjee K, Chmelik M, Davies J. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>","apa":"Chatterjee, K., Chmelik, M., &#38; Davies, J. (2015). <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>","ieee":"K. Chatterjee, M. Chmelik, and J. Davies, <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Jessica Davies. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>."},"publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"month":"11","oa":1,"status":"public","day":"06","ddc":["000"],"_id":"5443","publication_status":"published","file":[{"creator":"system","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:05Z","content_type":"application/pdf","file_id":"5466","date_updated":"2020-07-14T12:46:57Z","file_name":"IST-2015-325-v2+1_main.pdf","checksum":"f0fa31ad8161ed655137e94012123ef9","file_size":412379}],"has_accepted_license":"1","year":"2015","page":"23","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach."}],"date_published":"2015-11-06T00:00:00Z","pubrep_id":"362","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"},{"last_name":"Davies","first_name":"Jessica","id":"378E0060-F248-11E8-B48F-1D18A9856A87","full_name":"Davies, Jessica"}],"related_material":{"record":[{"id":"1166","status":"public","relation":"later_version"}]},"doi":"10.15479/AT:IST-2015-325-v2-1","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-21T16:24:05Z","oa_version":"Published Version","date_created":"2018-12-12T11:39:22Z","file_date_updated":"2020-07-14T12:46:57Z","department":[{"_id":"KrCh"}],"title":"A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs","publisher":"IST Austria"},{"author":[{"first_name":"Johannes","last_name":"Reiter","orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Makohon-Moore, Alvin","first_name":"Alvin","last_name":"Makohon-Moore"},{"last_name":"Gerold","first_name":"Jeffrey","full_name":"Gerold, Jeffrey"},{"last_name":"Bozic","first_name":"Ivana","full_name":"Bozic, Ivana"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Christine","last_name":"Iacobuzio-Donahue","full_name":"Iacobuzio-Donahue, Christine"},{"full_name":"Vogelstein, Bert","last_name":"Vogelstein","first_name":"Bert"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"date_published":"2015-12-30T00:00:00Z","pubrep_id":"399","doi":"10.15479/AT:IST-2015-399-v1-1","date_updated":"2020-07-14T23:05:07Z","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.","lang":"eng"}],"department":[{"_id":"KrCh"}],"title":"Reconstructing robust phylogenies of metastatic cancers","file_date_updated":"2020-07-14T12:46:58Z","publisher":"IST Austria","oa_version":"Published Version","date_created":"2018-12-12T11:39:22Z","oa":1,"status":"public","day":"30","ddc":["000","576"],"citation":{"apa":"Reiter, J., Makohon-Moore, A., Gerold, J., Bozic, I., Chatterjee, K., Iacobuzio-Donahue, C., … Nowak, M. (2015). <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>","ieee":"J. Reiter <i>et al.</i>, <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria, 2015.","chicago":"Reiter, Johannes, Alvin Makohon-Moore, Jeffrey Gerold, Ivana Bozic, Krishnendu Chatterjee, Christine Iacobuzio-Donahue, Bert Vogelstein, and Martin Nowak. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>.","mla":"Reiter, Johannes, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>.","short":"J. Reiter, A. Makohon-Moore, J. Gerold, I. Bozic, K. Chatterjee, C. Iacobuzio-Donahue, B. Vogelstein, M. Nowak, Reconstructing Robust Phylogenies of Metastatic Cancers, IST Austria, 2015.","ista":"Reiter J, Makohon-Moore A, Gerold J, Bozic I, Chatterjee K, Iacobuzio-Donahue C, Vogelstein B, Nowak M. 2015. Reconstructing robust phylogenies of metastatic cancers, IST Austria, 25p.","ama":"Reiter J, Makohon-Moore A, Gerold J, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>"},"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"month":"12","page":"25","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5444","publication_status":"published","has_accepted_license":"1","file":[{"date_created":"2018-12-12T11:53:24Z","content_type":"application/pdf","creator":"system","access_level":"open_access","relation":"main_file","file_name":"IST-2015-399-v1+1_treeomics.pdf","checksum":"c47d33bdda06181753c0af36f16e7b5d","file_size":3533200,"date_updated":"2020-07-14T12:46:58Z","file_id":"5485"}],"year":"2015"},{"oa":1,"status":"public","citation":{"ieee":"A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015.","chicago":"Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>.","apa":"Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>","ama":"Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. 2015. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>","short":"A. Fellner, (2015).","ista":"Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","mla":"Fellner, Andreas. <i>Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes</i>. Institute of Science and Technology Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"research_data","contributor":[{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Kretinsky"}],"has_accepted_license":"1","year":"2015","_id":"5549","abstract":[{"text":"This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.\r\nThe archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.\r\nTo execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.\r\nThe archive contains scripts that (if run often enough) reproduces the data presented in the publication.","lang":"eng"}],"publisher":"Institute of Science and Technology Austria","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes","publist_id":"5564","date_created":"2018-12-12T12:31:29Z","ec_funded":1,"oa_version":"Published Version","ddc":["004"],"day":"13","datarep_id":"28","month":"08","project":[{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"license":"https://creativecommons.org/publicdomain/zero/1.0/","file":[{"relation":"main_file","creator":"system","access_level":"open_access","content_type":"application/zip","date_created":"2018-12-12T13:02:31Z","file_id":"5597","date_updated":"2020-07-14T12:47:00Z","file_size":49557109,"file_name":"IST-2015-28-v1+2_Fellner_DataRep.zip","checksum":"b8bcb43c0893023cda66c1b69c16ac62"}],"article_processing_charge":"No","doi":"10.15479/AT:ISTA:28","date_updated":"2024-02-21T13:52:07Z","related_material":{"record":[{"relation":"popular_science","status":"public","id":"1603"}]},"author":[{"last_name":"Fellner","first_name":"Andreas","id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","full_name":"Fellner, Andreas"}],"date_published":"2015-08-13T00:00:00Z","keyword":["Markov Decision Process","Decision Tree","Probabilistic Verification","Counterexample Explanation"],"file_date_updated":"2020-07-14T12:47:00Z","tmp":{"short":"CC0 (1.0)","image":"/images/cc_0.png","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)"}},{"main_file_link":[{"open_access":"1","url":"https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9523/9300"}],"intvolume":"         2","publication_status":"published","day":"01","month":"01","language":[{"iso":"eng"}],"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"conference":{"location":"Austin, TX, USA","start_date":"2015-01-25","name":"AAAI: Conference on Artificial Intelligence","end_date":"2015-01-30"},"date_published":"2015-01-01T00:00:00Z","author":[{"last_name":"Ahmed","first_name":"Umair","full_name":"Ahmed, Umair"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Gulwani, Sumit","first_name":"Sumit","last_name":"Gulwani"}],"article_processing_charge":"No","date_updated":"2023-02-23T12:25:07Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5410"}]},"scopus_import":1,"quality_controlled":"1","volume":2,"page":"745 - 752","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","_id":"1481","year":"2015","oa":1,"acknowledgement":"A Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/146.\r\n","status":"public","citation":{"ama":"Ahmed U, Chatterjee K, Gulwani S. Automatic generation of alternative starting positions for simple traditional board games. In: <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>. Vol 2. AAAI Press; 2015:745-752.","ista":"Ahmed U, Chatterjee K, Gulwani S. 2015. Automatic generation of alternative starting positions for simple traditional board games. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 2, 745–752.","short":"U. Ahmed, K. Chatterjee, S. Gulwani, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 745–752.","mla":"Ahmed, Umair, et al. “Automatic Generation of Alternative Starting Positions for Simple Traditional Board Games.” <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, vol. 2, AAAI Press, 2015, pp. 745–52.","ieee":"U. Ahmed, K. Chatterjee, and S. Gulwani, “Automatic generation of alternative starting positions for simple traditional board games,” in <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, Austin, TX, USA, 2015, vol. 2, pp. 745–752.","chicago":"Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. “Automatic Generation of Alternative Starting Positions for Simple Traditional Board Games.” In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, 2:745–52. AAAI Press, 2015.","apa":"Ahmed, U., Chatterjee, K., &#38; Gulwani, S. (2015). Automatic generation of alternative starting positions for simple traditional board games. In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i> (Vol. 2, pp. 745–752). Austin, TX, USA: AAAI Press."},"publication":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence","title":"Automatic generation of alternative starting positions for simple traditional board games","department":[{"_id":"KrCh"}],"publisher":"AAAI Press","date_created":"2018-12-11T11:52:16Z","ec_funded":1,"oa_version":"None","publist_id":"5713","abstract":[{"text":"Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like 4×4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased. ","lang":"eng"}]},{"abstract":[{"lang":"eng","text":"We consider weighted automata with both positive and negative integer weights on edges and\r\nstudy the problem of synchronization using adaptive strategies that may only observe whether\r\nthe current weight-level is negative or nonnegative. We show that the synchronization problem is decidable in polynomial time for deterministic weighted automata."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"Polynomial time decidability of weighted synchronization under partial observability","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publist_id":"5680","oa_version":"Published Version","ec_funded":1,"date_created":"2018-12-11T11:52:22Z","status":"public","acknowledgement":"The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement 601148 (CASSTING), EU FP7 FET project SENSATION, Sino-Danish Basic Research Center IDAE4CPS, the European Research Council (ERC) under grant agreement 267989 (QUAREM), the Austrian Science Fund (FWF) project S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), the Czech Science Foundation under grant agreement P202/12/G061, and People Programme (Marie Curie Actions) of the European Union’s Seventh Framework\r\nProgramme (FP7/2007-2013) REA Grant No 291734.","oa":1,"citation":{"apa":"Kretinsky, J., Larsen, K., Laursen, S., &#38; Srba, J. (2015). Polynomial time decidability of weighted synchronization under partial observability (Vol. 42, pp. 142–154). Presented at the CONCUR: Concurrency Theory, Madrid, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">https://doi.org/10.4230/LIPIcs.CONCUR.2015.142</a>","chicago":"Kretinsky, Jan, Kim Larsen, Simon Laursen, and Jiří Srba. “Polynomial Time Decidability of Weighted Synchronization under Partial Observability,” 42:142–54. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">https://doi.org/10.4230/LIPIcs.CONCUR.2015.142</a>.","ieee":"J. Kretinsky, K. Larsen, S. Laursen, and J. Srba, “Polynomial time decidability of weighted synchronization under partial observability,” presented at the CONCUR: Concurrency Theory, Madrid, Spain, 2015, vol. 42, pp. 142–154.","ista":"Kretinsky J, Larsen K, Laursen S, Srba J. 2015. Polynomial time decidability of weighted synchronization under partial observability. CONCUR: Concurrency Theory, LIPIcs, vol. 42, 142–154.","short":"J. Kretinsky, K. Larsen, S. Laursen, J. Srba, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 142–154.","mla":"Kretinsky, Jan, et al. <i>Polynomial Time Decidability of Weighted Synchronization under Partial Observability</i>. Vol. 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 142–54, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">10.4230/LIPIcs.CONCUR.2015.142</a>.","ama":"Kretinsky J, Larsen K, Laursen S, Srba J. Polynomial time decidability of weighted synchronization under partial observability. In: Vol 42. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:142-154. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">10.4230/LIPIcs.CONCUR.2015.142</a>"},"type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"142 - 154","volume":42,"has_accepted_license":"1","year":"2015","_id":"1499","date_updated":"2021-01-12T06:51:10Z","doi":"10.4230/LIPIcs.CONCUR.2015.142","alternative_title":["LIPIcs"],"pubrep_id":"498","author":[{"last_name":"Kretinsky","orcid":"0000-0002-8122-2881","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"},{"full_name":"Larsen, Kim","last_name":"Larsen","first_name":"Kim"},{"full_name":"Laursen, Simon","last_name":"Laursen","first_name":"Simon"},{"full_name":"Srba, Jiří","last_name":"Srba","first_name":"Jiří"}],"date_published":"2015-01-01T00:00:00Z","quality_controlled":"1","scopus_import":1,"file_date_updated":"2020-07-14T12:44:58Z","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"location":"Madrid, Spain","start_date":"2015-09-01","name":"CONCUR: Concurrency Theory","end_date":"2015-09-04"},"day":"01","ddc":["000","003"],"language":[{"iso":"eng"}],"project":[{"call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425"},{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"month":"01","license":"https://creativecommons.org/licenses/by/4.0/","publication_status":"published","file":[{"creator":"system","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T10:08:12Z","content_type":"application/pdf","date_updated":"2020-07-14T12:44:58Z","file_id":"4672","file_name":"IST-2016-498-v1+1_32.pdf","checksum":"49eb5021caafaabe5356c65b9c5f8c9c","file_size":623563}],"intvolume":"        42"},{"citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Przemyslaw Daca. “CEGAR for Compositional Analysis of Qualitative Properties in Markov Decision Processes.” <i>Formal Methods in System Design</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s10703-015-0235-2\">https://doi.org/10.1007/s10703-015-0235-2</a>.","ieee":"K. Chatterjee, M. Chmelik, and P. Daca, “CEGAR for compositional analysis of qualitative properties in Markov decision processes,” <i>Formal Methods in System Design</i>, vol. 47, no. 2. Springer, pp. 230–264, 2015.","apa":"Chatterjee, K., Chmelik, M., &#38; Daca, P. (2015). CEGAR for compositional analysis of qualitative properties in Markov decision processes. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-015-0235-2\">https://doi.org/10.1007/s10703-015-0235-2</a>","ama":"Chatterjee K, Chmelik M, Daca P. CEGAR for compositional analysis of qualitative properties in Markov decision processes. <i>Formal Methods in System Design</i>. 2015;47(2):230-264. doi:<a href=\"https://doi.org/10.1007/s10703-015-0235-2\">10.1007/s10703-015-0235-2</a>","ista":"Chatterjee K, Chmelik M, Daca P. 2015. CEGAR for compositional analysis of qualitative properties in Markov decision processes. Formal Methods in System Design. 47(2), 230–264.","short":"K. Chatterjee, M. Chmelik, P. Daca, Formal Methods in System Design 47 (2015) 230–264.","mla":"Chatterjee, Krishnendu, et al. “CEGAR for Compositional Analysis of Qualitative Properties in Markov Decision Processes.” <i>Formal Methods in System Design</i>, vol. 47, no. 2, Springer, 2015, pp. 230–64, doi:<a href=\"https://doi.org/10.1007/s10703-015-0235-2\">10.1007/s10703-015-0235-2</a>."},"issue":"2","oa":1,"acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No. P23499- N23, FWF NFN Grant No. S11407-N23, FWF Grant S11403-N23 (RiSE), and FWF Grant Z211-N23 (Wittgenstein Award), ERC Start Grant (279307: Graph Games), Microsoft faculty fellows award, the ERC Advanced Grant QUAREM (Quantitative Reactive Modeling).","status":"public","year":"2015","_id":"1501","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"230 - 264","volume":47,"abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of two-player games by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We show a tight link between two-player games and MDPs, and as a consequence the results for games are lifted to MDPs with qualitative properties. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"publist_id":"5677","oa_version":"Preprint","date_created":"2018-12-11T11:52:23Z","ec_funded":1,"publisher":"Springer","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"CEGAR for compositional analysis of qualitative properties in Markov decision processes","publication":"Formal Methods in System Design","language":[{"iso":"eng"}],"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling"}],"month":"10","day":"01","publication_status":"published","main_file_link":[{"url":"https://arxiv.org/abs/1405.0835","open_access":"1"}],"intvolume":"        47","quality_controlled":"1","scopus_import":1,"related_material":{"record":[{"id":"1155","status":"public","relation":"dissertation_contains"}]},"date_updated":"2023-09-07T11:58:33Z","doi":"10.1007/s10703-015-0235-2","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","last_name":"Daca","first_name":"Przemyslaw"}],"date_published":"2015-10-01T00:00:00Z"},{"publication_status":"published","file":[{"file_size":467561,"file_name":"IST-2016-625-v1+1_conf-cbse-BenesDHKN15.pdf","checksum":"c6ce681035c163a158751f240cb7d389","file_id":"5303","date_updated":"2020-07-14T12:44:59Z","content_type":"application/pdf","date_created":"2018-12-12T10:17:46Z","relation":"main_file","creator":"system","access_level":"open_access"}],"project":[{"grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"The Wittgenstein Prize"},{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"language":[{"iso":"eng"}],"month":"05","day":"01","ddc":["000"],"conference":{"start_date":"2015-05-04","location":"Montreal, QC, Canada","end_date":"2015-05-08","name":"CBSE: Component-Based Software Engineering "},"file_date_updated":"2020-07-14T12:44:59Z","quality_controlled":"1","scopus_import":1,"date_updated":"2023-09-07T11:58:33Z","alternative_title":["Proceedings of the 18th International ACM SIGSOFT Symposium on Component-Based Software Engineering "],"doi":"10.1145/2737166.2737175","related_material":{"record":[{"id":"1155","relation":"dissertation_contains","status":"public"}]},"author":[{"full_name":"Beneš, Nikola","last_name":"Beneš","first_name":"Nikola"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A"},{"full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881"},{"full_name":"Nickovic, Dejan","last_name":"Nickovic","first_name":"Dejan"}],"pubrep_id":"625","date_published":"2015-05-01T00:00:00Z","year":"2015","has_accepted_license":"1","_id":"1502","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"101 - 110","publication_identifier":{"isbn":["978-1-4503-3471-6"]},"citation":{"ieee":"N. Beneš, P. Daca, T. A. Henzinger, J. Kretinsky, and D. Nickovic, “Complete composition operators for IOCO-testing theory,” presented at the CBSE: Component-Based Software Engineering , Montreal, QC, Canada, 2015, pp. 101–110.","chicago":"Beneš, Nikola, Przemyslaw Daca, Thomas A Henzinger, Jan Kretinsky, and Dejan Nickovic. “Complete Composition Operators for IOCO-Testing Theory,” 101–10. ACM, 2015. <a href=\"https://doi.org/10.1145/2737166.2737175\">https://doi.org/10.1145/2737166.2737175</a>.","apa":"Beneš, N., Daca, P., Henzinger, T. A., Kretinsky, J., &#38; Nickovic, D. (2015). Complete composition operators for IOCO-testing theory (pp. 101–110). Presented at the CBSE: Component-Based Software Engineering , Montreal, QC, Canada: ACM. <a href=\"https://doi.org/10.1145/2737166.2737175\">https://doi.org/10.1145/2737166.2737175</a>","ama":"Beneš N, Daca P, Henzinger TA, Kretinsky J, Nickovic D. Complete composition operators for IOCO-testing theory. In: ACM; 2015:101-110. doi:<a href=\"https://doi.org/10.1145/2737166.2737175\">10.1145/2737166.2737175</a>","short":"N. Beneš, P. Daca, T.A. Henzinger, J. Kretinsky, D. Nickovic, in:, ACM, 2015, pp. 101–110.","ista":"Beneš N, Daca P, Henzinger TA, Kretinsky J, Nickovic D. 2015. Complete composition operators for IOCO-testing theory. CBSE: Component-Based Software Engineering , Proceedings of the 18th International ACM SIGSOFT Symposium on Component-Based Software Engineering , , 101–110.","mla":"Beneš, Nikola, et al. <i>Complete Composition Operators for IOCO-Testing Theory</i>. ACM, 2015, pp. 101–10, doi:<a href=\"https://doi.org/10.1145/2737166.2737175\">10.1145/2737166.2737175</a>."},"status":"public","acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23(RiSE) and Z211-N23 (Wittgestein Award), by People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement 291734, and by the ARTEMIS JU under grant agreement 295373 (nSafeCer).  Jan Křetínský has been partially supported by the Czech Science Foundation, grant No.  P202/12/G061.  Nikola Beneš has been supported by the\r\nMEYS project No. CZ.1.07/2.3.00/30.0009 Employment of Newly Graduated Doctors of Science for Scientific Excellence.","oa":1,"publist_id":"5676","oa_version":"Submitted Version","date_created":"2018-12-11T11:52:24Z","ec_funded":1,"publisher":"ACM","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"title":"Complete composition operators for IOCO-testing theory","abstract":[{"lang":"eng","text":"We extend the theory of input-output conformance with operators for merge and quotient. The former is useful when testing against multiple requirements or views. The latter can be used to generate tests for patches of an already tested system. Both operators can combine systems with different action alphabets, which is usually the case when constructing complex systems and specifications from parts, for instance different views as well as newly defined functionality of a~previous version of the system."}]},{"abstract":[{"text":"There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant)will take over a resident population?We derive precise complexity results for a variety of scenarios. We therefore show that some fundamental questions in this area cannot be answered by simple equations (assuming that P is not equal to NP).","lang":"eng"}],"publisher":"National Academy of Sciences","title":"Computational complexity of ecological and evolutionary spatial dynamics","department":[{"_id":"KrCh"}],"publication":"PNAS","publist_id":"5612","oa_version":"Submitted Version","date_created":"2018-12-11T11:52:43Z","external_id":{"pmid":["26644569"]},"issue":"51","status":"public","oa":1,"citation":{"apa":"Ibsen-Jensen, R., Chatterjee, K., &#38; Nowak, M. (2015). Computational complexity of ecological and evolutionary spatial dynamics. <i>PNAS</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1511366112\">https://doi.org/10.1073/pnas.1511366112</a>","ieee":"R. Ibsen-Jensen, K. Chatterjee, and M. Nowak, “Computational complexity of ecological and evolutionary spatial dynamics,” <i>PNAS</i>, vol. 112, no. 51. National Academy of Sciences, pp. 15636–15641, 2015.","chicago":"Ibsen-Jensen, Rasmus, Krishnendu Chatterjee, and Martin Nowak. “Computational Complexity of Ecological and Evolutionary Spatial Dynamics.” <i>PNAS</i>. National Academy of Sciences, 2015. <a href=\"https://doi.org/10.1073/pnas.1511366112\">https://doi.org/10.1073/pnas.1511366112</a>.","short":"R. Ibsen-Jensen, K. Chatterjee, M. Nowak, PNAS 112 (2015) 15636–15641.","ista":"Ibsen-Jensen R, Chatterjee K, Nowak M. 2015. Computational complexity of ecological and evolutionary spatial dynamics. PNAS. 112(51), 15636–15641.","mla":"Ibsen-Jensen, Rasmus, et al. “Computational Complexity of Ecological and Evolutionary Spatial Dynamics.” <i>PNAS</i>, vol. 112, no. 51, National Academy of Sciences, 2015, pp. 15636–41, doi:<a href=\"https://doi.org/10.1073/pnas.1511366112\">10.1073/pnas.1511366112</a>.","ama":"Ibsen-Jensen R, Chatterjee K, Nowak M. Computational complexity of ecological and evolutionary spatial dynamics. <i>PNAS</i>. 2015;112(51):15636-15641. doi:<a href=\"https://doi.org/10.1073/pnas.1511366112\">10.1073/pnas.1511366112</a>"},"type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"15636 - 15641","volume":112,"year":"2015","_id":"1559","doi":"10.1073/pnas.1511366112","date_updated":"2021-01-12T06:51:36Z","date_published":"2015-12-22T00:00:00Z","author":[{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"quality_controlled":"1","scopus_import":1,"day":"22","pmid":1,"language":[{"iso":"eng"}],"month":"12","publication_status":"published","intvolume":"       112","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4697423/","open_access":"1"}]}]