[{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"related_material":{"record":[{"relation":"earlier_version","id":"5421","status":"public"},{"status":"public","id":"5432","relation":"earlier_version"}]},"file_date_updated":"2020-07-14T12:46:56Z","title":"The complexity of evolutionary games on graphs","status":"public","type":"technical_report","oa_version":"Published Version","publisher":"IST Austria","month":"06","publication_status":"published","date_updated":"2023-02-23T12:26:10Z","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."}],"page":"18","year":"2015","language":[{"iso":"eng"}],"pubrep_id":"338","date_published":"2015-06-16T00:00:00Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2015-323-v2-2","day":"16","file":[{"file_name":"IST-2015-323-v2+2_main.pdf","file_id":"5484","checksum":"66aace7d367032af97c15e35c9be9636","content_type":"application/pdf","date_created":"2018-12-12T11:53:23Z","access_level":"open_access","creator":"system","file_size":466161,"date_updated":"2020-07-14T12:46:56Z","relation":"main_file"}],"alternative_title":["IST Austria Technical Report"],"citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. 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-v2-2\">10.15479/AT:IST-2015-323-v2-2</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-v2-2\">https://doi.org/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.","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>","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","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>"},"_id":"5440","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"has_accepted_license":"1","ddc":["005","576"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:21Z"},{"ddc":["000"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:21Z","citation":{"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.","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>","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>","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.","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>.","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>.","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."},"alternative_title":["IST Austria Technical Report"],"_id":"5441","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir","last_name":"Goharshady","full_name":"Goharshady, Amir","orcid":"0000-0003-1702-6584"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis"}],"has_accepted_license":"1","day":"11","file":[{"file_name":"IST-2015-340-v1+1_main.pdf","date_updated":"2020-07-14T12:46:56Z","relation":"main_file","file_size":861396,"date_created":"2018-12-12T11:54:09Z","creator":"system","access_level":"open_access","file_id":"5531","content_type":"application/pdf","checksum":"df383dc62c94d7b2ea639aba088a76c6"}],"language":[{"iso":"eng"}],"pubrep_id":"340","department":[{"_id":"KrCh"}],"date_published":"2015-07-11T00:00:00Z","doi":"10.15479/AT:IST-2015-340-v1-1","page":"24","year":"2015","publisher":"IST Austria","month":"07","publication_status":"published","date_updated":"2025-04-15T08:11:48Z","abstract":[{"lang":"eng","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."}],"oa_version":"Published Version","related_material":{"record":[{"id":"5442","status":"public","relation":"earlier_version"},{"relation":"later_version","id":"6009","status":"public"},{"relation":"later_version","status":"public","id":"1437"}]},"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:56Z","status":"public","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","type":"technical_report"},{"day":"14","file":[{"creator":"system","date_created":"2018-12-12T11:53:37Z","access_level":"open_access","content_type":"application/pdf","checksum":"98fd936102f3e057fc321ef6d316001d","file_id":"5498","relation":"main_file","date_updated":"2020-07-14T12:46:57Z","file_size":658747,"file_name":"IST-2015-343-v2+1_main.pdf"},{"file_name":"IST-2015-343-v2+2_anonymous.txt","date_created":"2019-04-16T12:36:08Z","creator":"dernst","access_level":"closed","file_id":"6316","checksum":"b31d09b1241b59c75e1f42dadf09d258","content_type":"text/plain","file_size":139,"relation":"main_file","date_updated":"2020-07-14T12:46:57Z"}],"date_published":"2015-07-14T00:00:00Z","pubrep_id":"344","scopus_import":1,"language":[{"iso":"eng"}],"date_created":"2018-12-12T11:39:21Z","publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"has_accepted_license":"1","author":[{"first_name":"1","last_name":"Anonymous","full_name":"Anonymous, 1"},{"first_name":"2","last_name":"Anonymous","full_name":"Anonymous, 2"},{"full_name":"Anonymous, 3","first_name":"3","last_name":"Anonymous"},{"full_name":"Anonymous, 4","first_name":"4","last_name":"Anonymous"}],"_id":"5442","citation":{"chicago":"Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015.","mla":"Anonymous, 1, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015.","ama":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria; 2015.","short":"1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.","apa":"Anonymous, 1, Anonymous, 2, Anonymous, 3, &#38; Anonymous, 4. (2015). <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria.","ista":"Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 22p.","ieee":"1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria, 2015."},"alternative_title":["IST Austria Technical Report"],"oa_version":"Published Version","type":"technical_report","file_date_updated":"2020-07-14T12:46:57Z","status":"public","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"later_version","id":"5441","status":"public"},{"relation":"later_version","id":"6009","status":"public"},{"relation":"later_version","id":"1437","status":"public"}]},"year":"2015","page":"22","abstract":[{"lang":"eng","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 properties that arise in program analysis.\r\nWe consider that each component of the concurrent system is a graph with constant treewidth, and it is known that the controlflow graphs of most programs have constant treewidth. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis problems (e.g., alias analysis). The study of multiple queries allows us to consider the tradeoff between the resource usage of the \\emph{one-time} preprocessing and for \\emph{each individual} query. The traditional approaches construct the product graph of all components and apply the best-known graph algorithm on the product. In the traditional approach, even the answer to a single query requires the transitive closure computation (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.\r\n\r\nOur 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, \r\neach 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 that show that the worst-case running times of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (such as improving \r\nthe worst-case bounds for the shortest path problem in general graphs whose current best-known bound has not been improved in five decades). Finally, we provide a prototype implementation of our algorithms which significantly outperforms the existing algorithmic methods on several benchmarks."}],"date_updated":"2025-04-15T08:11:49Z","publication_status":"published","month":"07","publisher":"IST Austria"},{"oa_version":"Published Version","oa":1,"related_material":{"record":[{"id":"1166","status":"public","relation":"later_version"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:57Z","status":"public","title":"A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs","type":"technical_report","year":"2015","page":"23","publisher":"IST Austria","month":"11","publication_status":"published","abstract":[{"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.","lang":"eng"}],"date_updated":"2025-06-25T11:52:13Z","day":"06","file":[{"date_created":"2018-12-12T11:53:05Z","creator":"system","access_level":"open_access","checksum":"f0fa31ad8161ed655137e94012123ef9","content_type":"application/pdf","file_id":"5466","relation":"main_file","date_updated":"2020-07-14T12:46:57Z","file_size":412379,"file_name":"IST-2015-325-v2+1_main.pdf"}],"language":[{"iso":"eng"}],"pubrep_id":"362","date_published":"2015-11-06T00:00:00Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2015-325-v2-1","ddc":["000"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:22Z","alternative_title":["IST Austria Technical Report"],"citation":{"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>.","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>.","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>","short":"K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015.","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>","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.","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."},"_id":"5443","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"id":"378E0060-F248-11E8-B48F-1D18A9856A87","full_name":"Davies, Jessica","first_name":"Jessica","last_name":"Davies"}],"has_accepted_license":"1"},{"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"type":"technical_report","status":"public","title":"Reconstructing robust phylogenies of metastatic cancers","file_date_updated":"2020-07-14T12:46:58Z","year":"2015","page":"25","month":"12","publisher":"IST Austria","date_updated":"2020-07-14T23:05:07Z","abstract":[{"lang":"eng","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."}],"publication_status":"published","day":"30","file":[{"file_name":"IST-2015-399-v1+1_treeomics.pdf","date_created":"2018-12-12T11:53:24Z","creator":"system","access_level":"open_access","file_id":"5485","checksum":"c47d33bdda06181753c0af36f16e7b5d","content_type":"application/pdf","file_size":3533200,"relation":"main_file","date_updated":"2020-07-14T12:46:58Z"}],"pubrep_id":"399","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2015-399-v1-1","date_published":"2015-12-30T00:00:00Z","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:22Z","publication_identifier":{"issn":["2664-1690"]},"ddc":["000","576"],"_id":"5444","citation":{"ieee":"J. Reiter <i>et al.</i>, <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria, 2015.","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>","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.","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>","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.","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>."},"alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","author":[{"id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter","first_name":"Johannes","full_name":"Reiter, Johannes","orcid":"0000-0002-0170-7353"},{"full_name":"Makohon-Moore, Alvin","last_name":"Makohon-Moore","first_name":"Alvin"},{"full_name":"Gerold, Jeffrey","last_name":"Gerold","first_name":"Jeffrey"},{"full_name":"Bozic, Ivana","last_name":"Bozic","first_name":"Ivana"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Iacobuzio-Donahue, Christine","first_name":"Christine","last_name":"Iacobuzio-Donahue"},{"full_name":"Vogelstein, Bert","last_name":"Vogelstein","first_name":"Bert"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}]},{"page":"51","year":"2015","month":"02","publisher":"IST Austria","date_updated":"2026-07-06T13:26:26Z","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."}],"publication_status":"published","oa_version":"Published Version","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"earlier_version","id":"5429","status":"public"},{"relation":"later_version","status":"public","id":"1657"},{"id":"466","status":"public","relation":"later_version"}]},"type":"technical_report","status":"public","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","file_date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:39:19Z","publication_identifier":{"issn":["2664-1690"]},"ddc":["004"],"_id":"5435","citation":{"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.","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>.","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>","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 51p.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">10.15479/AT:IST-2015-318-v2-1</a>","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015."},"alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","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","first_name":"Zuzana","last_name":"Komarkova"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","first_name":"Jan","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan"}],"day":"23","file":[{"file_id":"5525","checksum":"75284adec80baabdfe71ff9ebbc27445","content_type":"application/pdf","date_created":"2018-12-12T11:54:03Z","access_level":"open_access","creator":"system","date_updated":"2020-07-14T12:46:53Z","relation":"main_file","file_size":717630,"file_name":"IST-2015-318-v2+1_main.pdf"}],"pubrep_id":"327","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2015-318-v2-1","date_published":"2015-02-23T00:00:00Z","department":[{"_id":"KrCh"}]},{"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.\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."}],"date_updated":"2026-07-06T13:26:26Z","publication_status":"published","month":"01","publisher":"IST Austria","page":"41","year":"2015","type":"technical_report","status":"public","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","file_date_updated":"2020-07-14T12:46:52Z","oa":1,"related_material":{"record":[{"status":"public","id":"5435","relation":"later_version"},{"id":"1657","status":"public","relation":"later_version"},{"id":"466","status":"public","relation":"later_version"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","has_accepted_license":"1","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Zuzana","last_name":"Komarkova","full_name":"Komarkova, Zuzana"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","first_name":"Jan","last_name":"Kretinsky"}],"_id":"5429","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.","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>","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">https://doi.org/10.15479/AT:IST-2015-318-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>.","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."},"alternative_title":["IST Austria Technical Report"],"date_created":"2018-12-12T11:39:17Z","publication_identifier":{"issn":["2664-1690"]},"ddc":["004"],"doi":"10.15479/AT:IST-2015-318-v1-1","department":[{"_id":"KrCh"}],"date_published":"2015-01-12T00:00:00Z","pubrep_id":"318","language":[{"iso":"eng"}],"file":[{"file_name":"IST-2015-318-v1+1_main.pdf","creator":"system","access_level":"open_access","date_created":"2018-12-12T11:54:11Z","file_id":"5533","checksum":"e4869a584567c506349abda9c8ec7db3","content_type":"application/pdf","file_size":689863,"date_updated":"2020-07-14T12:46:52Z","relation":"main_file"}],"day":"12"},{"pubrep_id":"334","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2015-334-v1-1","date_published":"2015-05-05T00:00:00Z","department":[{"_id":"KrCh"}],"file":[{"file_id":"5518","checksum":"8a5f2d77560e552af87eb1982437a43b","content_type":"application/pdf","date_created":"2018-12-12T11:53:56Z","access_level":"open_access","creator":"system","relation":"main_file","date_updated":"2020-07-14T12:46:55Z","file_size":422573,"file_name":"IST-2015-334-v1+1_report.pdf"}],"day":"05","_id":"5438","alternative_title":["IST Austria Technical Report"],"citation":{"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>","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015.","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>","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>.","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."},"has_accepted_license":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus"},{"first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-12T11:39:20Z","ddc":["004"],"publication_identifier":{"issn":["2664-1690"]},"oa":1,"related_material":{"record":[{"relation":"later_version","id":"1610","status":"public"},{"id":"465","status":"public","relation":"later_version"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","file_date_updated":"2020-07-14T12:46:55Z","status":"public","title":"Edit distance for pushdown automata","oa_version":"Published Version","month":"05","publisher":"IST Austria","abstract":[{"lang":"eng","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. "}],"date_updated":"2026-07-06T13:27:53Z","publication_status":"published","year":"2015","page":"15"},{"page":"29","year":"2015","publication_status":"published","date_updated":"2026-07-07T14:01:10Z","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"}],"publisher":"IST Austria","month":"04","oa_version":"Published Version","file_date_updated":"2020-07-14T12:46:54Z","status":"public","title":"Nested weighted automata","type":"technical_report","related_material":{"record":[{"status":"public","id":"5415","relation":"earlier_version"},{"status":"public","id":"1656","relation":"later_version"},{"relation":"later_version","id":"467","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"date_created":"2018-12-12T11:39:19Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"has_accepted_license":"1","citation":{"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>.","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>.","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>","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p.","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>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2015."},"alternative_title":["IST Austria Technical Report"],"_id":"5436","file":[{"access_level":"open_access","date_created":"2018-12-12T11:54:19Z","creator":"system","content_type":"application/pdf","file_id":"5541","checksum":"3c402f47d3669c28d04d1af405a08e3f","file_size":569991,"relation":"main_file","date_updated":"2020-07-14T12:46:54Z","file_name":"IST-2015-170-v2+2_report.pdf"}],"day":"24","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_published":"2015-04-24T00:00:00Z","doi":"10.15479/AT:IST-2015-170-v2-2","language":[{"iso":"eng"}],"pubrep_id":"331"},{"citation":{"apa":"Daca, P., Henzinger, T. A., Krenn, W., &#38; Nickovic, D. (2014). <i>Compositional specifications for IOCO testing</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">https://doi.org/10.15479/AT:IST-2014-148-v2-1</a>","ista":"Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications for IOCO testing, IST Austria, 20p.","short":"P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, Compositional Specifications for IOCO Testing, IST Austria, 2014.","ama":"Daca P, Henzinger TA, Krenn W, Nickovic D. <i>Compositional Specifications for IOCO Testing</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">10.15479/AT:IST-2014-148-v2-1</a>","mla":"Daca, Przemyslaw, et al. <i>Compositional Specifications for IOCO Testing</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">10.15479/AT:IST-2014-148-v2-1</a>.","chicago":"Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic. <i>Compositional Specifications for IOCO Testing</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">https://doi.org/10.15479/AT:IST-2014-148-v2-1</a>.","ieee":"P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, <i>Compositional specifications for IOCO testing</i>. IST Austria, 2014."},"alternative_title":["IST Austria Technical Report"],"_id":"5411","author":[{"full_name":"Daca, Przemyslaw","last_name":"Daca","first_name":"Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger"},{"full_name":"Krenn, Willibald","last_name":"Krenn","first_name":"Willibald"},{"first_name":"Dejan","last_name":"Nickovic","full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"date_created":"2018-12-12T11:39:11Z","language":[{"iso":"eng"}],"pubrep_id":"152","department":[{"_id":"ToHe"}],"date_published":"2014-01-28T00:00:00Z","doi":"10.15479/AT:IST-2014-148-v2-1","day":"28","file":[{"file_name":"IST-2014-148-v2+1_main_tr.pdf","content_type":"application/pdf","checksum":"0e03aba625cc334141a3148432aa5760","file_id":"5543","access_level":"open_access","creator":"system","date_created":"2018-12-12T11:54:21Z","file_size":534732,"date_updated":"2020-07-14T12:46:46Z","relation":"main_file"}],"publisher":"IST Austria","month":"01","publication_status":"published","date_updated":"2025-09-29T11:40:47Z","abstract":[{"text":"Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing.\r\nIn this paper, we study compositional properties of the IOCO-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the IOCO conformance relation, the resulting methodology can be applied to a broader class of systems.","lang":"eng"}],"page":"20","year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"later_version","id":"2167","status":"public"}]},"oa":1,"title":"Compositional specifications for IOCO testing","status":"public","file_date_updated":"2020-07-14T12:46:46Z","type":"technical_report","oa_version":"Published Version"},{"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"5413","status":"public","relation":"later_version"},{"id":"5414","status":"public","relation":"later_version"},{"id":"2063","status":"public","relation":"later_version"}]},"type":"technical_report","file_date_updated":"2020-07-14T12:46:47Z","title":"CEGAR for qualitative analysis of probabilistic systems","status":"public","oa_version":"Published Version","month":"01","publisher":"IST Austria","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"date_updated":"2025-04-15T07:56:48Z","publication_status":"published","year":"2014","page":"31","pubrep_id":"153","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-153-v1-1","department":[{"_id":"KrCh"}],"date_published":"2014-01-29T00:00:00Z","day":"29","file":[{"date_updated":"2020-07-14T12:46:47Z","relation":"main_file","file_size":423322,"file_id":"5500","checksum":"4d6cda4bebed970926403ad6ad8c745f","content_type":"application/pdf","creator":"system","date_created":"2018-12-12T11:53:39Z","access_level":"open_access","file_name":"IST-2014-153-v1+1_main.pdf"}],"_id":"5412","alternative_title":["IST Austria Technical Report"],"citation":{"ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 31p.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014."},"has_accepted_license":"1","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-12T11:39:11Z","ddc":["000"],"publication_identifier":{"issn":["2664-1690"]}},{"language":[{"iso":"eng"}],"pubrep_id":"164","date_published":"2014-02-06T00:00:00Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2014-153-v2-2","file":[{"file_name":"IST-2014-153-v2+2_main.pdf","content_type":"application/pdf","checksum":"ce4967a184d84863eec76c66cbac1614","file_id":"5539","date_created":"2018-12-12T11:54:17Z","creator":"system","access_level":"open_access","file_size":606049,"date_updated":"2020-07-14T12:46:47Z","relation":"main_file"}],"day":"06","alternative_title":["IST Austria Technical Report"],"citation":{"ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>"},"_id":"5413","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"date_created":"2018-12-12T11:39:11Z","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"earlier_version","id":"5412","status":"public"},{"status":"public","id":"5414","relation":"later_version"},{"relation":"later_version","status":"public","id":"2063"}]},"file_date_updated":"2020-07-14T12:46:47Z","title":"CEGAR for qualitative analysis of probabilistic systems","status":"public","type":"technical_report","oa_version":"Published Version","publisher":"IST Austria","month":"02","publication_status":"published","date_updated":"2025-04-15T07:56:48Z","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"page":"33","year":"2014"},{"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014."},"alternative_title":["IST Austria Technical Report"],"_id":"5414","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","last_name":"Daca","first_name":"Przemyslaw"},{"full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"has_accepted_license":"1","ddc":["000"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:12Z","language":[{"iso":"eng"}],"pubrep_id":"165","date_published":"2014-02-07T00:00:00Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2014-153-v3-1","day":"07","file":[{"file_name":"IST-2014-153-v3+1_main.pdf","file_id":"5464","checksum":"87b93fe9af71fc5c94b0eb6151537e11","content_type":"application/pdf","access_level":"open_access","creator":"system","date_created":"2018-12-12T11:53:03Z","file_size":606227,"relation":"main_file","date_updated":"2020-07-14T12:46:48Z"}],"publisher":"IST Austria","month":"02","publication_status":"published","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"date_updated":"2025-04-15T07:56:48Z","page":"33","year":"2014","oa":1,"related_material":{"record":[{"id":"5412","status":"public","relation":"earlier_version"},{"status":"public","id":"5413","relation":"earlier_version"},{"relation":"later_version","id":"2063","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"CEGAR for qualitative analysis of probabilistic systems","file_date_updated":"2020-07-14T12:46:48Z","status":"public","type":"technical_report","oa_version":"Published Version"},{"title":"Model measuring for hybrid systems","status":"public","file_date_updated":"2020-07-14T12:46:49Z","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"later_version","status":"public","id":"2217"}]},"oa":1,"oa_version":"Published Version","publication_status":"published","date_updated":"2025-06-26T08:32:32Z","abstract":[{"text":"As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem.","lang":"eng"}],"publisher":"IST Austria","month":"02","page":"22","year":"2014","department":[{"_id":"ToHe"}],"date_published":"2014-02-19T00:00:00Z","doi":"10.15479/AT:IST-2014-171-v1-1","language":[{"iso":"eng"}],"pubrep_id":"171","day":"19","file":[{"file_name":"IST-2014-171-v1+1_report.pdf","file_id":"5492","checksum":"445456d22371e4e49aad2b9a0c13bf80","content_type":"application/pdf","date_created":"2018-12-12T11:53:32Z","access_level":"open_access","creator":"system","relation":"main_file","date_updated":"2020-07-14T12:46:49Z","file_size":712077}],"author":[{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"citation":{"ieee":"T. A. Henzinger and J. Otop, <i>Model measuring for hybrid systems</i>. IST Austria, 2014.","short":"T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria, 2014.","ama":"Henzinger TA, Otop J. <i>Model Measuring for Hybrid Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>","ista":"Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria, 22p.","apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>Model measuring for hybrid systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>","chicago":"Henzinger, Thomas A, and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>.","mla":"Henzinger, Thomas A., and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>."},"_id":"5416","ddc":["005"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:12Z"},{"doi":"10.15479/AT:IST-2014-172-v1-1","department":[{"_id":"ToHe"}],"date_published":"2014-02-19T00:00:00Z","pubrep_id":"175","language":[{"iso":"eng"}],"file":[{"file_name":"IST-2014-172-v1+1_report.pdf","date_created":"2018-12-12T11:53:20Z","creator":"system","access_level":"open_access","content_type":"application/pdf","checksum":"fcc3eab903cfcd3778b338d2d0d44d18","file_id":"5481","file_size":383052,"date_updated":"2020-07-14T12:46:49Z","relation":"main_file"}],"day":"19","has_accepted_license":"1","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"last_name":"Otop","first_name":"Jan","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"_id":"5417","alternative_title":["IST Austria Technical Report"],"citation":{"ama":"Henzinger TA, Otop J. <i>From Model Checking to Model Measuring</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>","short":"T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria, 2014.","ista":"Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria, 14p.","apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>From model checking to model measuring</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>","chicago":"Henzinger, Thomas A, and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>.","mla":"Henzinger, Thomas A., and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>.","ieee":"T. A. Henzinger and J. Otop, <i>From model checking to model measuring</i>. IST Austria, 2014."},"date_created":"2018-12-12T11:39:13Z","ddc":["000"],"publication_identifier":{"issn":["2664-1690"]},"type":"technical_report","file_date_updated":"2020-07-14T12:46:49Z","title":"From model checking to model measuring","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"later_version","status":"public","id":"2327"}]},"oa":1,"oa_version":"Published Version","date_updated":"2024-10-21T06:02:58Z","abstract":[{"text":"We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.\r\nThe model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.\r\nWe show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.\r\nWe use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. \r\nWe give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.","lang":"eng"}],"publication_status":"published","month":"02","publisher":"IST Austria","page":"14","year":"2014"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"related_material":{"record":[{"relation":"later_version","id":"2163","status":"public"}]},"type":"technical_report","file_date_updated":"2020-07-14T12:46:49Z","status":"public","title":"Games with a weak adversary","oa_version":"Published Version","month":"03","publisher":"IST Austria","abstract":[{"text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results.","lang":"eng"}],"date_updated":"2025-04-15T07:55:59Z","publication_status":"published","year":"2014","page":"18","pubrep_id":"176","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-176-v1-1","date_published":"2014-03-22T00:00:00Z","department":[{"_id":"KrCh"}],"file":[{"file_name":"IST-2014-176-v1+1_icalp_14.pdf","checksum":"1d6958aa60050e1c3e932c6e5f34c39f","content_type":"application/pdf","file_id":"5468","date_created":"2018-12-12T11:53:07Z","access_level":"open_access","creator":"system","relation":"main_file","date_updated":"2020-07-14T12:46:49Z","file_size":328253}],"day":"22","_id":"5418","alternative_title":["IST Austria Technical Report"],"citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>.","ama":"Chatterjee K, Doyen L. <i>Games with a Weak Adversary</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014.","apa":"Chatterjee, K., &#38; Doyen, L. (2014). <i>Games with a weak adversary</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.","ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014."},"has_accepted_license":"1","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"}],"date_created":"2018-12-12T11:39:13Z","publication_identifier":{"issn":["2664-1690"]},"ddc":["000","005"]},{"page":"34","year":"2014","publication_status":"published","date_updated":"2021-01-12T08:02:03Z","abstract":[{"text":"We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:\r\n1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).\r\n2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.\r\nOur algorithms improve all existing results, and use very simple data structures.","lang":"eng"}],"publisher":"IST Austria","month":"04","oa_version":"Published Version","status":"public","file_date_updated":"2020-07-14T12:46:50Z","title":"Improved algorithms for reachability and shortest path on low tree-width graphs","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"ddc":["000"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:13Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas"}],"has_accepted_license":"1","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria, 2014."},"alternative_title":["IST Austria Technical Report"],"_id":"5419","day":"14","file":[{"file_id":"5548","content_type":"application/pdf","checksum":"c608e66030a4bf51d2d99b451f539b99","creator":"system","access_level":"open_access","date_created":"2018-12-12T11:54:25Z","date_updated":"2020-07-14T12:46:50Z","relation":"main_file","file_size":670031,"file_name":"IST-2014-187-v1+1_main_full_tech.pdf"}],"department":[{"_id":"KrCh"}],"date_published":"2014-04-14T00:00:00Z","doi":"10.15479/AT:IST-2014-187-v1-1","language":[{"iso":"eng"}],"pubrep_id":"187"},{"date_published":"2014-04-14T00:00:00Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2014-191-v1-1","language":[{"iso":"eng"}],"pubrep_id":"191","day":"14","file":[{"file_name":"IST-2014-191-v1+1_main_full.pdf","creator":"system","date_created":"2018-12-12T11:53:58Z","access_level":"open_access","checksum":"49e0fd3e62650346daf7dc04604f7a0a","file_id":"5520","content_type":"application/pdf","date_updated":"2020-07-14T12:46:50Z","relation":"main_file","file_size":584368}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"citation":{"ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria, 2014.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>."},"_id":"5420","ddc":["000","005"],"publication_identifier":{"issn":["2664-1690"]},"date_created":"2018-12-12T11:39:14Z","file_date_updated":"2020-07-14T12:46:50Z","status":"public","title":"The value 1 problem for concurrent mean-payoff games","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"oa_version":"Published Version","publication_status":"published","date_updated":"2021-01-12T08:02:05Z","abstract":[{"lang":"eng","text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy)."}],"publisher":"IST Austria","month":"04","page":"49","year":"2014"},{"year":"2014","page":"27","publication_status":"published","date_updated":"2023-02-23T12:26:33Z","abstract":[{"lang":"eng","text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time."}],"publisher":"IST Austria","month":"04","oa_version":"Published Version","file_date_updated":"2020-07-14T12:46:50Z","title":"The complexity of evolution on graphs","status":"public","type":"technical_report","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"related_material":{"record":[{"status":"public","id":"5432","relation":"later_version"},{"id":"5440","status":"public","relation":"later_version"}]},"publication_identifier":{"issn":["2664-1690"]},"ddc":["000","005"],"date_created":"2018-12-12T11:39:14Z","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"citation":{"chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on Graphs, IST Austria, 2014.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolution on Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2014). <i>The complexity of evolution on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolution on graphs</i>. IST Austria, 2014."},"_id":"5421","file":[{"file_size":443529,"date_updated":"2020-07-14T12:46:50Z","relation":"main_file","file_id":"5538","content_type":"application/pdf","checksum":"42f3d8b563286eb0d903832bd9a848d3","access_level":"open_access","creator":"system","date_created":"2018-12-12T11:54:16Z","file_name":"IST-2014-190-v2+2_main_full.pdf"},{"file_name":"IST-2014-190-v1+1_main_full.pdf","access_level":"open_access","creator":"kschuh","date_created":"2019-09-06T07:30:20Z","file_id":"6852","content_type":"application/pdf","checksum":"0c9a2fd822309719634495a35957e34d","date_updated":"2020-07-14T12:46:50Z","relation":"main_file","file_size":440911}],"day":"18","department":[{"_id":"KrCh"}],"date_published":"2014-04-18T00:00:00Z","doi":"10.15479/AT:IST-2014-190-v2-2","language":[{"iso":"eng"}],"pubrep_id":"190"},{"publication_identifier":{"issn":["2664-1690"]},"ddc":["005"],"date_created":"2018-12-12T11:39:15Z","citation":{"ieee":"K. Chatterjee, A. Kössler, A. Pavlogiannis, and U. Schmid, <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Alexander Kössler, Andreas Pavlogiannis, and Ulrich Schmid. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>.","ista":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. 2014. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks, IST Austria, 14p.","apa":"Chatterjee, K., Kössler, A., Pavlogiannis, A., &#38; Schmid, U. (2014). <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>","ama":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>","short":"K. Chatterjee, A. Kössler, A. Pavlogiannis, U. Schmid, A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks, IST Austria, 2014."},"alternative_title":["IST Austria Technical Report"],"_id":"5423","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kössler, Alexander","first_name":"Alexander","last_name":"Kössler"},{"last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ulrich","last_name":"Schmid","full_name":"Schmid, Ulrich"}],"has_accepted_license":"1","file":[{"file_size":1270021,"date_updated":"2020-07-14T12:46:50Z","relation":"main_file","content_type":"application/pdf","file_id":"5514","checksum":"4b8fde4d9ef6653837f6803921d83032","creator":"system","access_level":"open_access","date_created":"2018-12-12T11:53:53Z","file_name":"IST-2014-300-v1+1_main.pdf"}],"day":"29","language":[{"iso":"eng"}],"pubrep_id":"300","date_published":"2014-07-29T00:00:00Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2014-300-v1-1","year":"2014","page":"14","publisher":"IST Austria","month":"07","publication_status":"published","date_updated":"2025-09-29T13:15:35Z","abstract":[{"lang":"eng","text":"We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. "}],"oa_version":"Published Version","oa":1,"related_material":{"record":[{"relation":"later_version","id":"1714","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:50Z","status":"public","title":"A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks","type":"technical_report"}]