[{"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis"}],"type":"technical_report","related_material":{"record":[{"relation":"earlier_version","id":"5430","status":"public"},{"status":"public","relation":"later_version","id":"1607"}]},"_id":"5437","page":"27","publication_status":"published","file_date_updated":"2020-07-14T12:46:54Z","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. \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. ","lang":"eng"}],"oa":1,"date_published":"2015-04-27T00:00:00Z","title":"Faster algorithms for quantitative verification in constant treewidth graphs","language":[{"iso":"eng"}],"month":"04","date_updated":"2025-09-23T08:47:23Z","publisher":"IST Austria","department":[{"_id":"KrCh"}],"date_created":"2018-12-12T11:39:19Z","year":"2015","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-330-v2-1","alternative_title":["IST Austria Technical Report"],"pubrep_id":"333","day":"27","status":"public","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-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>.","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>.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.","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>"},"file":[{"creator":"system","date_created":"2018-12-12T11:53:12Z","file_name":"IST-2015-330-v2+1_main.pdf","content_type":"application/pdf","checksum":"f5917c20f84018b362d385c000a2e123","relation":"main_file","access_level":"open_access","file_size":1072137,"date_updated":"2020-07-14T12:46:54Z","file_id":"5473"}],"has_accepted_license":"1","ddc":["000"]},{"has_accepted_license":"1","ddc":["005","576"],"citation":{"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>.","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>","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>.","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.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015."},"file":[{"access_level":"open_access","relation":"main_file","checksum":"66aace7d367032af97c15e35c9be9636","date_updated":"2020-07-14T12:46:56Z","file_size":466161,"file_id":"5484","creator":"system","date_created":"2018-12-12T11:53:23Z","content_type":"application/pdf","file_name":"IST-2015-323-v2+2_main.pdf"}],"alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2015-323-v2-2","publication_identifier":{"issn":["2664-1690"]},"status":"public","day":"16","pubrep_id":"338","year":"2015","date_created":"2018-12-12T11:39:21Z","month":"06","language":[{"iso":"eng"}],"title":"The complexity of evolutionary games on graphs","date_published":"2015-06-16T00:00:00Z","department":[{"_id":"KrCh"}],"publisher":"IST Austria","date_updated":"2023-02-23T12:26:10Z","page":"18","oa":1,"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."}],"file_date_updated":"2020-07-14T12:46:56Z","publication_status":"published","related_material":{"record":[{"status":"public","id":"5421","relation":"earlier_version"},{"id":"5432","relation":"earlier_version","status":"public"}]},"_id":"5440","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"oa_version":"Published Version","type":"technical_report"},{"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"orcid":"0000-0003-1702-6584","id":"391365CE-F248-11E8-B48F-1D18A9856A87","full_name":"Goharshady, Amir","last_name":"Goharshady","first_name":"Amir"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","first_name":"Andreas"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","type":"technical_report","_id":"5441","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5442"},{"id":"6009","relation":"later_version","status":"public"},{"id":"1437","relation":"later_version","status":"public"}]},"page":"24","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"}],"oa":1,"publication_status":"published","file_date_updated":"2020-07-14T12:46:56Z","language":[{"iso":"eng"}],"title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","month":"07","date_published":"2015-07-11T00:00:00Z","department":[{"_id":"KrCh"}],"publisher":"IST Austria","date_updated":"2025-04-15T08:11:48Z","year":"2015","date_created":"2018-12-12T11:39:21Z","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2015-340-v1-1","publication_identifier":{"issn":["2664-1690"]},"pubrep_id":"340","status":"public","day":"11","citation":{"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>","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>.","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>.","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.","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.","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>","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."},"file":[{"file_id":"5531","access_level":"open_access","checksum":"df383dc62c94d7b2ea639aba088a76c6","relation":"main_file","date_updated":"2020-07-14T12:46:56Z","file_size":861396,"date_created":"2018-12-12T11:54:09Z","content_type":"application/pdf","file_name":"IST-2015-340-v1+1_main.pdf","creator":"system"}],"has_accepted_license":"1","ddc":["000"]},{"has_accepted_license":"1","ddc":["000"],"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>.","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>","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>.","short":"K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015.","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.","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>","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."},"file":[{"creator":"system","date_created":"2018-12-12T11:53:05Z","content_type":"application/pdf","file_name":"IST-2015-325-v2+1_main.pdf","access_level":"open_access","checksum":"f0fa31ad8161ed655137e94012123ef9","relation":"main_file","file_size":412379,"date_updated":"2020-07-14T12:46:57Z","file_id":"5466"}],"alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-325-v2-1","pubrep_id":"362","status":"public","day":"06","year":"2015","date_created":"2018-12-12T11:39:22Z","title":"A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs","language":[{"iso":"eng"}],"month":"11","date_published":"2015-11-06T00:00:00Z","department":[{"_id":"KrCh"}],"publisher":"IST Austria","date_updated":"2025-06-25T11:52:13Z","page":"23","oa":1,"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."}],"publication_status":"published","file_date_updated":"2020-07-14T12:46:57Z","_id":"5443","related_material":{"record":[{"status":"public","id":"1166","relation":"later_version"}]},"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik"},{"full_name":"Davies, Jessica","id":"378E0060-F248-11E8-B48F-1D18A9856A87","first_name":"Jessica","last_name":"Davies"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","type":"technical_report"},{"year":"2015","date_created":"2018-12-12T11:39:22Z","alternative_title":["IST Austria Technical Report"],"publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-399-v1-1","status":"public","pubrep_id":"399","day":"30","citation":{"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>","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.","ieee":"J. Reiter <i>et al.</i>, <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria, 2015.","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.","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>.","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>.","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>"},"file":[{"file_id":"5485","date_updated":"2020-07-14T12:46:58Z","file_size":3533200,"access_level":"open_access","relation":"main_file","checksum":"c47d33bdda06181753c0af36f16e7b5d","file_name":"IST-2015-399-v1+1_treeomics.pdf","content_type":"application/pdf","date_created":"2018-12-12T11:53:24Z","creator":"system"}],"has_accepted_license":"1","ddc":["000","576"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Johannes","last_name":"Reiter","full_name":"Reiter, Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","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"},{"last_name":"Bozic","first_name":"Ivana","full_name":"Bozic, Ivana"},{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Iacobuzio-Donahue","first_name":"Christine","full_name":"Iacobuzio-Donahue, Christine"},{"full_name":"Vogelstein, Bert","first_name":"Bert","last_name":"Vogelstein"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"oa_version":"Published Version","type":"technical_report","_id":"5444","page":"25","oa":1,"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"}],"file_date_updated":"2020-07-14T12:46:58Z","publication_status":"published","title":"Reconstructing robust phylogenies of metastatic cancers","month":"12","language":[{"iso":"eng"}],"date_published":"2015-12-30T00:00:00Z","department":[{"_id":"KrCh"}],"publisher":"IST Austria","date_updated":"2020-07-14T23:05:07Z"},{"file_date_updated":"2020-07-14T12:47:00Z","oa":1,"date_updated":"2025-09-23T08:23:15Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"Institute of Science and Technology Austria","date_published":"2015-08-13T00:00:00Z","month":"08","type":"research_data","oa_version":"Published Version","_id":"5549","publist_id":"5564","project":[{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"}],"citation":{"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>","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>.","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.","short":"A. Fellner, (2015).","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>.","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>","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>."},"tmp":{"legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","image":"/images/cc_0.png","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)"},"ec_funded":1,"status":"public","day":"13","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"}],"license":"https://creativecommons.org/publicdomain/zero/1.0/","article_processing_charge":"No","keyword":["Markov Decision Process","Decision Tree","Probabilistic Verification","Counterexample Explanation"],"title":"Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes","author":[{"full_name":"Fellner, Andreas","id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","last_name":"Fellner","first_name":"Andreas"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","relation":"popular_science","id":"1603"}]},"file":[{"creator":"system","content_type":"application/zip","file_name":"IST-2015-28-v1+2_Fellner_DataRep.zip","date_created":"2018-12-12T13:02:31Z","date_updated":"2020-07-14T12:47:00Z","file_size":49557109,"checksum":"b8bcb43c0893023cda66c1b69c16ac62","relation":"main_file","access_level":"open_access","file_id":"5597"}],"ddc":["004"],"has_accepted_license":"1","contributor":[{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Kretinsky"}],"date_created":"2018-12-12T12:31:29Z","datarep_id":"28","year":"2015","doi":"10.15479/AT:ISTA:28"},{"project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF","name":"Game Theory"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, in:, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2015, pp. 1018–1029.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The value 1 problem under finite-memory strategies for concurrent mean-payoff games,” in <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, San Diego, CA, United States, 2015, vol. 2015, no. 1, pp. 1018–1029.","ama":"Chatterjee K, Ibsen-Jensen R. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In: <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2015. SIAM; 2015:1018-1029. doi:<a href=\"https://doi.org/10.1137/1.9781611973730.69\">10.1137/1.9781611973730.69</a>","ista":"Chatterjee K, Ibsen-Jensen R. 2015. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2015, 1018–1029.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2015, pp. 1018–1029). San Diego, CA, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611973730.69\">https://doi.org/10.1137/1.9781611973730.69</a>","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” In <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2015:1018–29. SIAM, 2015. <a href=\"https://doi.org/10.1137/1.9781611973730.69\">https://doi.org/10.1137/1.9781611973730.69</a>.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2015, no. 1, SIAM, 2015, pp. 1018–29, doi:<a href=\"https://doi.org/10.1137/1.9781611973730.69\">10.1137/1.9781611973730.69</a>."},"OA_type":"green","ec_funded":1,"day":"01","status":"public","oa":1,"publisher":"SIAM","department":[{"_id":"KrCh"}],"arxiv":1,"date_updated":"2025-06-26T06:54:08Z","language":[{"iso":"eng"}],"month":"01","date_published":"2015-01-01T00:00:00Z","acknowledgement":"The research was partly supported by FWF Grant No P 23499-N23, FWF NFN Grant\r\nNo S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","type":"conference","intvolume":"      2015","oa_version":"Preprint","_id":"10796","scopus_import":"1","quality_controlled":"1","corr_author":"1","conference":{"start_date":"2015-01-04","name":"SODA: Symposium on Discrete Algorithms","end_date":"2015-01-06","location":"San Diego, CA, United States"},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1409.6690","open_access":"1"}],"year":"2015","date_created":"2022-02-25T12:18:43Z","publication":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms","issue":"1","publication_identifier":{"isbn":["978-161197374-7"]},"doi":"10.1137/1.9781611973730.69","abstract":[{"text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).","lang":"eng"}],"external_id":{"arxiv":["1409.6690"]},"publication_status":"published","page":"1018-1029","article_processing_charge":"No","title":"The value 1 problem under finite-memory strategies for concurrent mean-payoff games","OA_place":"publisher","volume":2015,"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF","name":"Game Theory"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Reactive Modeling","call_identifier":"FP7","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"grant_number":"215543","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","name":"COMponent-Based Embedded Systems design Techniques","call_identifier":"FP7"},{"_id":"25F1337C-B435-11E9-9278-68D0E5697425","grant_number":"214373","call_identifier":"FP7","name":"Design for Embedded Systems"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"}],"citation":{"ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger, “Randomness for free,” <i>Information and Computation</i>, vol. 245, no. 12. Elsevier, pp. 3–16, 2015.","short":"K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, Information and Computation 245 (2015) 3–16.","ista":"Chatterjee K, Doyen L, Gimbert H, Henzinger TA. 2015. Randomness for free. Information and Computation. 245(12), 3–16.","ama":"Chatterjee K, Doyen L, Gimbert H, Henzinger TA. Randomness for free. <i>Information and Computation</i>. 2015;245(12):3-16. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">10.1016/j.ic.2015.06.003</a>","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Thomas A Henzinger. “Randomness for Free.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">https://doi.org/10.1016/j.ic.2015.06.003</a>.","apa":"Chatterjee, K., Doyen, L., Gimbert, H., &#38; Henzinger, T. A. (2015). Randomness for free. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">https://doi.org/10.1016/j.ic.2015.06.003</a>","mla":"Chatterjee, Krishnendu, et al. “Randomness for Free.” <i>Information and Computation</i>, vol. 245, no. 12, Elsevier, 2015, pp. 3–16, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.06.003\">10.1016/j.ic.2015.06.003</a>."},"status":"public","day":"01","ec_funded":1,"publisher":"Elsevier","arxiv":1,"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_updated":"2025-09-23T10:32:00Z","month":"12","language":[{"iso":"eng"}],"date_published":"2015-12-01T00:00:00Z","oa":1,"isi":1,"_id":"1731","scopus_import":"1","publist_id":"5395","type":"journal_article","intvolume":"       245","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1006.0673"}],"quality_controlled":"1","corr_author":"1","publication":"Information and Computation","issue":"12","doi":"10.1016/j.ic.2015.06.003","year":"2015","date_created":"2018-12-11T11:53:42Z","title":"Randomness for free","abstract":[{"text":"We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games. ","lang":"eng"}],"external_id":{"isi":["000368899100002"],"arxiv":["1006.0673"]},"publication_status":"published","page":"3 - 16","article_processing_charge":"No","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"3856"}]},"volume":245,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"last_name":"Gimbert","first_name":"Hugo","full_name":"Gimbert, Hugo"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"}]},{"oa":1,"publisher":"IEEE","arxiv":1,"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:25:52Z","month":"01","language":[{"iso":"eng"}],"date_published":"2015-01-01T00:00:00Z","type":"conference","oa_version":"Preprint","_id":"1732","scopus_import":1,"publist_id":"5394","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IEEE, 2015, pp. 325–30, doi:<a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">10.1109/ICRA.2015.7139019</a>.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications,” 325–30. IEEE, 2015. <a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">https://doi.org/10.1109/ICRA.2015.7139019</a>.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2015). Qualitative analysis of POMDPs with temporal logic specifications for robotics applications (pp. 325–330). Presented at the ICRA: International Conference on Robotics and Automation, Seattle, WA, United States: IEEE. <a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">https://doi.org/10.1109/ICRA.2015.7139019</a>","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. In: IEEE; 2015:325-330. doi:<a href=\"https://doi.org/10.1109/ICRA.2015.7139019\">10.1109/ICRA.2015.7139019</a>","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. ICRA: International Conference on Robotics and Automation, 325–330.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, IEEE, 2015, pp. 325–330.","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Qualitative analysis of POMDPs with temporal logic specifications for robotics applications,” presented at the ICRA: International Conference on Robotics and Automation, Seattle, WA, United States, 2015, pp. 325–330."},"ec_funded":1,"day":"01","status":"public","abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty."}],"external_id":{"arxiv":["1409.3360"]},"publication_status":"published","page":"325 - 330","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"},{"last_name":"Gupta","first_name":"Raghav","full_name":"Gupta, Raghav"},{"first_name":"Ayush","last_name":"Kanodia","full_name":"Kanodia, Ayush"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"earlier_version","id":"5424","status":"public"},{"id":"5426","relation":"earlier_version","status":"public"}]},"quality_controlled":"1","conference":{"start_date":"2015-05-26","name":"ICRA: International Conference on Robotics and Automation","location":"Seattle, WA, United States","end_date":"2015-05-30"},"main_file_link":[{"url":"http://arxiv.org/abs/1409.3360","open_access":"1"}],"year":"2015","date_created":"2018-12-11T11:53:43Z","doi":"10.1109/ICRA.2015.7139019"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Roderick","last_name":"Bloem","full_name":"Bloem, Roderick"},{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Jacobs, Swen","last_name":"Jacobs","first_name":"Swen"},{"first_name":"Robert","last_name":"Könighofer","full_name":"Könighofer, Robert"}],"volume":9035,"title":"Assume-guarantee synthesis for concurrent reactive programs with partial information","article_processing_charge":"No","page":"517 - 532","external_id":{"arxiv":["1411.4604"]},"publication_status":"published","abstract":[{"lang":"eng","text":"Synthesis of program parts is particularly useful for concurrent systems. However, most approaches do not support common design tasks, like modifying a single process without having to re-synthesize or verify the whole system. Assume-guarantee synthesis (AGS) provides robustness against modifications of system parts, but thus far has been limited to the perfect information setting. This means that local variables cannot be hidden from other processes, which renders synthesis results cumbersome or even impossible to realize.We resolve this shortcoming by defining AGS under partial information. We analyze the complexity and decidability in different settings, showing that the problem has a high worstcase complexity and is undecidable in many interesting cases. Based on these observations, we present a pragmatic algorithm based on bounded synthesis, and demonstrate its practical applicability on several examples."}],"doi":"10.1007/978-3-662-46681-0_50","date_created":"2018-12-11T11:54:17Z","year":"2015","main_file_link":[{"url":"http://arxiv.org/abs/1411.4604","open_access":"1"}],"conference":{"start_date":"2015-04-11","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","end_date":"2015-04-18","location":"London, United Kingdom"},"publist_id":"5264","scopus_import":"1","_id":"1838","intvolume":"      9035","oa_version":"Preprint","type":"conference","acknowledgement":"This work was supported by the Austrian Science Fund (FWF) through the research network RiSE (S11406-N23, S11407-N23) and grant nr. P23499-N23, by the European Commission through an ERC Start grant (279307: Graph Games) and project STANCE (317753), as well as by the German Research Foundation (DFG) through SFB/TR 14 AVACS and project ASDPS(JA 2357/2-1).","date_published":"2015-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"date_updated":"2025-06-11T07:09:03Z","department":[{"_id":"KrCh"}],"publisher":"Springer","arxiv":1,"oa":1,"alternative_title":["LNCS"],"day":"01","status":"public","ec_funded":1,"citation":{"ieee":"R. Bloem, K. Chatterjee, S. Jacobs, and R. Könighofer, “Assume-guarantee synthesis for concurrent reactive programs with partial information,” presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, London, United Kingdom, 2015, vol. 9035, pp. 517–532.","short":"R. Bloem, K. Chatterjee, S. Jacobs, R. Könighofer, in:, Springer, 2015, pp. 517–532.","ista":"Bloem R, Chatterjee K, Jacobs S, Könighofer R. 2015. Assume-guarantee synthesis for concurrent reactive programs with partial information. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 9035, 517–532.","ama":"Bloem R, Chatterjee K, Jacobs S, Könighofer R. Assume-guarantee synthesis for concurrent reactive programs with partial information. In: Vol 9035. Springer; 2015:517-532. doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">10.1007/978-3-662-46681-0_50</a>","apa":"Bloem, R., Chatterjee, K., Jacobs, S., &#38; Könighofer, R. (2015). Assume-guarantee synthesis for concurrent reactive programs with partial information (Vol. 9035, pp. 517–532). Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, London, United Kingdom: Springer. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">https://doi.org/10.1007/978-3-662-46681-0_50</a>","chicago":"Bloem, Roderick, Krishnendu Chatterjee, Swen Jacobs, and Robert Könighofer. “Assume-Guarantee Synthesis for Concurrent Reactive Programs with Partial Information,” 9035:517–32. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">https://doi.org/10.1007/978-3-662-46681-0_50</a>.","mla":"Bloem, Roderick, et al. <i>Assume-Guarantee Synthesis for Concurrent Reactive Programs with Partial Information</i>. Vol. 9035, Springer, 2015, pp. 517–32, doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_50\">10.1007/978-3-662-46681-0_50</a>."},"project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"}]},{"main_file_link":[{"url":"http://arxiv.org/abs/1501.03093","open_access":"1"}],"conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2015-04-11","location":"London, United Kingdom","end_date":"2015-04-18"},"quality_controlled":"1","doi":"10.1007/978-3-662-46681-0_12","date_created":"2018-12-11T11:54:18Z","year":"2015","title":"Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives","article_processing_charge":"No","page":"181 - 187","external_id":{"arxiv":["1501.03093"]},"publication_status":"published","abstract":[{"text":"We present MultiGain, a tool to synthesize strategies for Markov decision processes (MDPs) with multiple mean-payoff objectives. Our models are described in PRISM, and our tool uses the existing interface and simulator of PRISM. Our tool extends PRISM by adding novel algorithms for multiple mean-payoff objectives, and also provides features such as (i) generating strategies and exploring them for simulation, and checking them with respect to other properties; and (ii) generating an approximate Pareto curve for two mean-payoff objectives. In addition, we present a new practical algorithm for the analysis of MDPs with multiple mean-payoff objectives under memoryless strategies.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Brázdil, Tomáš","first_name":"Tomáš","last_name":"Brázdil"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Forejt, Vojtěch","first_name":"Vojtěch","last_name":"Forejt"},{"last_name":"Kučera","first_name":"Antonín","full_name":"Kučera, Antonín"}],"volume":9035,"citation":{"mla":"Brázdil, Tomáš, et al. <i>Multigain: A Controller Synthesis Tool for MDPs with Multiple Mean-Payoff Objectives</i>. Vol. 9035, Springer, 2015, pp. 181–87, doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">10.1007/978-3-662-46681-0_12</a>.","apa":"Brázdil, T., Chatterjee, K., Forejt, V., &#38; Kučera, A. (2015). Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives. Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, London, United Kingdom: Springer. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">https://doi.org/10.1007/978-3-662-46681-0_12</a>","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Multigain: A Controller Synthesis Tool for MDPs with Multiple Mean-Payoff Objectives.” Lecture Notes in Computer Science. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">https://doi.org/10.1007/978-3-662-46681-0_12</a>.","ama":"Brázdil T, Chatterjee K, Forejt V, Kučera A. Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives. 2015;9035:181-187. doi:<a href=\"https://doi.org/10.1007/978-3-662-46681-0_12\">10.1007/978-3-662-46681-0_12</a>","ista":"Brázdil T, Chatterjee K, Forejt V, Kučera A. 2015. Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives. 9035, 181–187.","short":"T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, 9035 (2015) 181–187.","ieee":"T. Brázdil, K. Chatterjee, V. Forejt, and A. Kučera, “Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives,” vol. 9035. Springer, pp. 181–187, 2015."},"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"}],"alternative_title":["LNCS"],"series_title":"Lecture Notes in Computer Science","day":"01","status":"public","ec_funded":1,"date_published":"2015-01-01T00:00:00Z","language":[{"iso":"eng"}],"month":"01","date_updated":"2025-06-11T07:09:21Z","publisher":"Springer","arxiv":1,"department":[{"_id":"KrCh"}],"oa":1,"publist_id":"5263","scopus_import":"1","_id":"1839","intvolume":"      9035","oa_version":"Preprint","type":"conference"},{"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus"},{"last_name":"Otop","first_name":"Jan","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"repository","volume":9135,"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5438"},{"id":"465","relation":"later_version","status":"public"}]},"article_processing_charge":"No","page":"121 - 133","publication_status":"published","external_id":{"arxiv":["1504.08259"],"isi":["000364317900010"]},"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. The problem of computing edit distance to pushdown automata 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"}],"title":"Edit distance for pushdown automata","date_created":"2018-12-11T11:53:01Z","year":"2015","publication_identifier":{"isbn":["978-3-662-47665-9"]},"doi":"10.1007/978-3-662-47666-6_10","issue":"Part II","publication":"42nd International Colloquium on Automata, Languages, and Programming","quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1504.08259","open_access":"1"}],"conference":{"end_date":"2015-07-10","location":"Kyoto, Japan","start_date":"2015-07-06","name":"ICALP: Automata, Languages and Programming"},"intvolume":"      9135","oa_version":"Preprint","acknowledgement":"This research was funded in part by the European Research Council (ERC) under\r\ngrant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects\r\nS11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), FWF Grant No P23499-\r\nN23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph\r\nGames), and MSR faculty fellows award.","type":"conference","publist_id":"5556","scopus_import":"1","_id":"1610","isi":1,"oa":1,"date_published":"2015-07-01T00:00:00Z","language":[{"iso":"eng"}],"month":"07","date_updated":"2026-07-06T13:27:53Z","arxiv":1,"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"Springer Nature","ec_funded":1,"OA_type":"green","alternative_title":["LNCS"],"status":"public","pubrep_id":"321","day":"01","citation":{"mla":"Chatterjee, Krishnendu, et al. “Edit Distance for Pushdown Automata.” <i>42nd International Colloquium on Automata, Languages, and Programming</i>, vol. 9135, no. Part II, Springer Nature, 2015, pp. 121–33, doi:<a href=\"https://doi.org/10.1007/978-3-662-47666-6_10\">10.1007/978-3-662-47666-6_10</a>.","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., &#38; Otop, J. (2015). Edit distance for pushdown automata. In <i>42nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 9135, pp. 121–133). Kyoto, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-47666-6_10\">https://doi.org/10.1007/978-3-662-47666-6_10</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. “Edit Distance for Pushdown Automata.” In <i>42nd International Colloquium on Automata, Languages, and Programming</i>, 9135:121–33. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47666-6_10\">https://doi.org/10.1007/978-3-662-47666-6_10</a>.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata. 42nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 9135, 121–133.","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown automata. In: <i>42nd International Colloquium on Automata, Languages, and Programming</i>. Vol 9135. Springer Nature; 2015:121-133. doi:<a href=\"https://doi.org/10.1007/978-3-662-47666-6_10\">10.1007/978-3-662-47666-6_10</a>","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International Colloquium on Automata, Languages, and Programming, Springer Nature, 2015, pp. 121–133.","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, “Edit distance for pushdown automata,” in <i>42nd International Colloquium on Automata, Languages, and Programming</i>, Kyoto, Japan, 2015, vol. 9135, no. Part II, pp. 121–133."},"project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}]},{"project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","call_identifier":"FP7"},{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"citation":{"apa":"Chatterjee, K., Komárková, Z., &#38; Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. Presented at the LICS: Logic in Computer Science, Kyoto, Japan: IEEE. <a href=\"https://doi.org/10.1109/LICS.2015.32\">https://doi.org/10.1109/LICS.2015.32</a>","chicago":"Chatterjee, Krishnendu, Zuzana Komárková, and Jan Kretinsky. “Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes.” LICS. IEEE, 2015. <a href=\"https://doi.org/10.1109/LICS.2015.32\">https://doi.org/10.1109/LICS.2015.32</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IEEE, 2015, pp. 244–56, doi:<a href=\"https://doi.org/10.1109/LICS.2015.32\">10.1109/LICS.2015.32</a>.","ieee":"K. Chatterjee, Z. Komárková, and J. Kretinsky, “Unifying two views on multiple mean-payoff objectives in Markov decision processes.” IEEE, pp. 244–256, 2015.","short":"K. Chatterjee, Z. Komárková, J. Kretinsky, (2015) 244–256.","ama":"Chatterjee K, Komárková Z, Kretinsky J. Unifying two views on multiple mean-payoff objectives in Markov decision processes. 2015:244-256. doi:<a href=\"https://doi.org/10.1109/LICS.2015.32\">10.1109/LICS.2015.32</a>","ista":"Chatterjee K, Komárková Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes. , 244–256."},"OA_type":"green","ec_funded":1,"day":"01","status":"public","series_title":"LICS","alternative_title":["LICS"],"oa":1,"isi":1,"publisher":"IEEE","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_updated":"2026-07-06T13:26:26Z","month":"07","language":[{"iso":"eng"}],"date_published":"2015-07-01T00:00:00Z","acknowledgement":"A Technical Report of this paper is available at DOI: 10.15479/AT:IST-2015-318-v1-1\r\n","type":"conference","oa_version":"Preprint","_id":"1657","scopus_import":"1","publist_id":"5493","quality_controlled":"1","conference":{"start_date":"2015-07-06","name":"LICS: Logic in Computer Science","end_date":"2015-07-10","location":"Kyoto, Japan"},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.15479/AT:IST-2015-318-v1-1"}],"year":"2015","date_created":"2018-12-11T11:53:18Z","doi":"10.1109/LICS.2015.32","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist 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. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., Ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems, 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. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem. "}],"publication_status":"published","external_id":{"isi":["000380427100024"]},"page":"244 - 256","article_processing_charge":"No","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","OA_place":"repository","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Komárková","first_name":"Zuzana","full_name":"Komárková, Zuzana"},{"last_name":"Kretinsky","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan"}],"related_material":{"record":[{"relation":"earlier_version","id":"5429","status":"public"},{"id":"5435","relation":"earlier_version","status":"public"},{"relation":"later_version","id":"466","status":"public"}]}},{"citation":{"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>","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>.","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria, 2015.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 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>"},"file":[{"date_updated":"2020-07-14T12:46:53Z","file_size":717630,"access_level":"open_access","checksum":"75284adec80baabdfe71ff9ebbc27445","relation":"main_file","file_id":"5525","creator":"system","file_name":"IST-2015-318-v2+1_main.pdf","content_type":"application/pdf","date_created":"2018-12-12T11:54:03Z"}],"has_accepted_license":"1","ddc":["004"],"date_created":"2018-12-12T11:39:19Z","year":"2015","doi":"10.15479/AT:IST-2015-318-v2-1","publication_identifier":{"issn":["2664-1690"]},"alternative_title":["IST Austria Technical Report"],"day":"23","status":"public","pubrep_id":"327","page":"51","file_date_updated":"2020-07-14T12:46:53Z","publication_status":"published","oa":1,"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."}],"date_published":"2015-02-23T00:00:00Z","month":"02","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","language":[{"iso":"eng"}],"date_updated":"2026-07-06T13:26:26Z","publisher":"IST Austria","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Komarkova","first_name":"Zuzana","full_name":"Komarkova, Zuzana"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","last_name":"Kretinsky","first_name":"Jan"}],"oa_version":"Published Version","type":"technical_report","_id":"5435","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5429"},{"status":"public","id":"1657","relation":"later_version"},{"status":"public","relation":"later_version","id":"466"}]}},{"citation":{"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>.","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>","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. <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.","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."},"file":[{"file_id":"5533","file_size":689863,"date_updated":"2020-07-14T12:46:52Z","access_level":"open_access","relation":"main_file","checksum":"e4869a584567c506349abda9c8ec7db3","file_name":"IST-2015-318-v1+1_main.pdf","content_type":"application/pdf","date_created":"2018-12-12T11:54:11Z","creator":"system"}],"has_accepted_license":"1","ddc":["004"],"year":"2015","date_created":"2018-12-12T11:39:17Z","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2015-318-v1-1","publication_identifier":{"issn":["2664-1690"]},"status":"public","pubrep_id":"318","day":"12","page":"41","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."}],"oa":1,"file_date_updated":"2020-07-14T12:46:52Z","publication_status":"published","language":[{"iso":"eng"}],"month":"01","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","date_published":"2015-01-12T00:00:00Z","publisher":"IST Austria","department":[{"_id":"KrCh"}],"date_updated":"2026-07-06T13:26:26Z","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Komarkova, Zuzana","first_name":"Zuzana","last_name":"Komarkova"},{"first_name":"Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"}],"type":"technical_report","_id":"5429","related_material":{"record":[{"status":"public","relation":"later_version","id":"5435"},{"relation":"later_version","id":"1657","status":"public"},{"status":"public","id":"466","relation":"later_version"}]}},{"publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-334-v1-1","alternative_title":["IST Austria Technical Report"],"day":"05","pubrep_id":"334","status":"public","date_created":"2018-12-12T11:39:20Z","year":"2015","has_accepted_license":"1","ddc":["004"],"citation":{"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>.","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.","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.","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, <i>Edit distance for pushdown automata</i>. IST Austria, 2015."},"file":[{"file_id":"5518","file_size":422573,"date_updated":"2020-07-14T12:46:55Z","relation":"main_file","checksum":"8a5f2d77560e552af87eb1982437a43b","access_level":"open_access","file_name":"IST-2015-334-v1+1_report.pdf","content_type":"application/pdf","date_created":"2018-12-12T11:53:56Z","creator":"system"}],"_id":"5438","related_material":{"record":[{"id":"1610","relation":"later_version","status":"public"},{"relation":"later_version","id":"465","status":"public"}]},"oa_version":"Published Version","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","date_published":"2015-05-05T00:00:00Z","title":"Edit distance for pushdown automata","language":[{"iso":"eng"}],"month":"05","date_updated":"2026-07-06T13:27:53Z","publisher":"IST Austria","department":[{"_id":"KrCh"}],"page":"15","publication_status":"published","file_date_updated":"2020-07-14T12:46:55Z","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. "}],"oa":1},{"related_material":{"record":[{"status":"public","relation":"later_version","id":"464"}]},"volume":"2015-July","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Loitzenbauer, Veronika","first_name":"Veronika","last_name":"Loitzenbauer"}],"title":"Improved algorithms for one-pair and k-pair Streett objectives","publication_status":"published","external_id":{"isi":["000380427100026"]},"abstract":[{"text":"The computation of the winning set for one-pair Streett objectives and for k-pair Streett objectives in (standard) graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formed ness of specifications, and the synthesis of reactive systems. We give faster algorithms for the computation of the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in game graphs and (2) for k-pair Streett objectives in graphs. For both problems this represents the first improvement in asymptotic running time in 15 years.","lang":"eng"}],"article_processing_charge":"No","publication":"Proceedings - Symposium on Logic in Computer Science","doi":"10.1109/LICS.2015.34","article_number":"7174888","date_created":"2018-12-11T11:53:19Z","year":"2015","conference":{"name":"LICS: Logic in Computer Science","start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan"},"main_file_link":[{"open_access":"1","url":"https://eprints.cs.univie.ac.at/4368/"}],"quality_controlled":"1","scopus_import":"1","_id":"1661","publist_id":"5489","type":"conference","acknowledgement":"K. C. is supported by the Austrian Science Fund (FWF): P23499-N23 and S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award. M. H. is supported by the Austrian Science Fund (FWF): P23499-N23 and the Vienna Science and Technology Fund (WWTF) grant ICT10-002. V. L. is supported by the Vienna Science and Technology Fund (WWTF) grant ICT10-002. The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 340506.","oa_version":"Submitted Version","date_updated":"2026-07-06T13:28:05Z","department":[{"_id":"KrCh"}],"publisher":"IEEE","date_published":"2015-07-01T00:00:00Z","language":[{"iso":"eng"}],"month":"07","oa":1,"isi":1,"status":"public","day":"01","ec_funded":1,"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” <i>Proceedings - Symposium on Logic in Computer Science</i>, vol. 2015–July, 7174888, IEEE, 2015, doi:<a href=\"https://doi.org/10.1109/LICS.2015.34\">10.1109/LICS.2015.34</a>.","chicago":"Chatterjee, Krishnendu, Monika Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” In <i>Proceedings - Symposium on Logic in Computer Science</i>, Vol. 2015–July. IEEE, 2015. <a href=\"https://doi.org/10.1109/LICS.2015.34\">https://doi.org/10.1109/LICS.2015.34</a>.","apa":"Chatterjee, K., Henzinger, M., &#38; Loitzenbauer, V. (2015). Improved algorithms for one-pair and k-pair Streett objectives. In <i>Proceedings - Symposium on Logic in Computer Science</i> (Vol. 2015–July). Kyoto, Japan: IEEE. <a href=\"https://doi.org/10.1109/LICS.2015.34\">https://doi.org/10.1109/LICS.2015.34</a>","ama":"Chatterjee K, Henzinger M, Loitzenbauer V. Improved algorithms for one-pair and k-pair Streett objectives. In: <i>Proceedings - Symposium on Logic in Computer Science</i>. Vol 2015-July. IEEE; 2015. doi:<a href=\"https://doi.org/10.1109/LICS.2015.34\">10.1109/LICS.2015.34</a>","ista":"Chatterjee K, Henzinger M, Loitzenbauer V. 2015. Improved algorithms for one-pair and k-pair Streett objectives. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174888.","short":"K. Chatterjee, M. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.","ieee":"K. Chatterjee, M. Henzinger, and V. Loitzenbauer, “Improved algorithms for one-pair and k-pair Streett objectives,” in <i>Proceedings - Symposium on Logic in Computer Science</i>, Kyoto, Japan, 2015, vol. 2015–July."}},{"type":"journal_article","intvolume":"       115","oa_version":"Preprint","_id":"2034","scopus_import":"1","publist_id":"5025","oa":1,"isi":1,"department":[{"_id":"KrCh"}],"publisher":"Elsevier","arxiv":1,"date_updated":"2026-07-07T13:10:27Z","month":"01","language":[{"iso":"eng"}],"date_published":"2015-01-01T00:00:00Z","ec_funded":1,"day":"01","status":"public","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"citation":{"ama":"Bérard B, Chatterjee K, Sznajder N. Probabilistic opacity for Markov decision processes. <i>Information Processing Letters</i>. 2015;115(1):52-59. doi:<a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">10.1016/j.ipl.2014.09.001</a>","ista":"Bérard B, Chatterjee K, Sznajder N. 2015. Probabilistic opacity for Markov decision processes. Information Processing Letters. 115(1), 52–59.","ieee":"B. Bérard, K. Chatterjee, and N. Sznajder, “Probabilistic opacity for Markov decision processes,” <i>Information Processing Letters</i>, vol. 115, no. 1. Elsevier, pp. 52–59, 2015.","short":"B. Bérard, K. Chatterjee, N. Sznajder, Information Processing Letters 115 (2015) 52–59.","mla":"Bérard, Béatrice, et al. “Probabilistic Opacity for Markov Decision Processes.” <i>Information Processing Letters</i>, vol. 115, no. 1, Elsevier, 2015, pp. 52–59, doi:<a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">10.1016/j.ipl.2014.09.001</a>.","apa":"Bérard, B., Chatterjee, K., &#38; Sznajder, N. (2015). Probabilistic opacity for Markov decision processes. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">https://doi.org/10.1016/j.ipl.2014.09.001</a>","chicago":"Bérard, Béatrice, Krishnendu Chatterjee, and Nathalie Sznajder. “Probabilistic Opacity for Markov Decision Processes.” <i>Information Processing Letters</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ipl.2014.09.001\">https://doi.org/10.1016/j.ipl.2014.09.001</a>."},"volume":115,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Bérard","first_name":"Béatrice","full_name":"Bérard, Béatrice"},{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Nathalie","last_name":"Sznajder","full_name":"Sznajder, Nathalie"}],"abstract":[{"text":"Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.","lang":"eng"}],"external_id":{"arxiv":["1407.4225"],"isi":["000345478700010"]},"publication_status":"published","page":"52 - 59","article_processing_charge":"No","title":"Probabilistic opacity for Markov decision processes","year":"2015","date_created":"2018-12-11T11:55:20Z","publication":"Information Processing Letters","das_tickbox":"1","issue":"1","doi":"10.1016/j.ipl.2014.09.001","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1407.4225","open_access":"1"}]},{"OA_type":"green","ec_funded":1,"status":"public","day":"31","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"citation":{"ama":"Chatterjee K, Henzinger TA, Otop J. Nested weighted automata. In: <i>Proceedings - Symposium on Logic in Computer Science</i>. Vol 2015-July. IEEE; 2015. doi:<a href=\"https://doi.org/10.1109/LICS.2015.72\">10.1109/LICS.2015.72</a>","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174926.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Nested weighted automata,” in <i>Proceedings - Symposium on Logic in Computer Science</i>, Kyoto, Japan, 2015, vol. 2015–July.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.","mla":"Chatterjee, Krishnendu, et al. “Nested Weighted Automata.” <i>Proceedings - Symposium on Logic in Computer Science</i>, vol. 2015–July, 7174926, IEEE, 2015, doi:<a href=\"https://doi.org/10.1109/LICS.2015.72\">10.1109/LICS.2015.72</a>.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2015). Nested weighted automata. In <i>Proceedings - Symposium on Logic in Computer Science</i> (Vol. 2015–July). Kyoto, Japan: IEEE. <a href=\"https://doi.org/10.1109/LICS.2015.72\">https://doi.org/10.1109/LICS.2015.72</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Nested Weighted Automata.” In <i>Proceedings - Symposium on Logic in Computer Science</i>, Vol. 2015–July. IEEE, 2015. <a href=\"https://doi.org/10.1109/LICS.2015.72\">https://doi.org/10.1109/LICS.2015.72</a>."},"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), Z211-N23 (Wittgenstein Award), FWF Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nA Technical Report of the paper is available at: \r\nhttps://repository.ist.ac.at/331/\r\n","type":"conference","oa_version":"Preprint","_id":"1656","scopus_import":"1","publist_id":"5494","oa":1,"isi":1,"publisher":"IEEE","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"arxiv":1,"date_updated":"2026-07-07T14:01:10Z","month":"07","language":[{"iso":"eng"}],"date_published":"2015-07-31T00:00:00Z","article_number":"7174926","year":"2015","date_created":"2018-12-11T11:53:17Z","publication":"Proceedings - Symposium on Logic in Computer Science","doi":"10.1109/LICS.2015.72","quality_controlled":"1","corr_author":"1","conference":{"end_date":"2015-07-10","location":"Kyoto, Japan","name":"LICS: Logic in Computer Science","start_date":"2015-07-06"},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1606.03598","open_access":"1"}],"volume":"2015-July","OA_place":"repository","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"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":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","related_material":{"record":[{"relation":"earlier_version","id":"5415","status":"public"},{"id":"5436","relation":"earlier_version","status":"public"},{"id":"467","relation":"later_version","status":"public"}]},"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. In 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"}],"external_id":{"isi":["000380427100064"],"arxiv":["1606.03598"]},"publication_status":"published","article_processing_charge":"No","title":"Nested weighted automata"},{"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5415"},{"relation":"later_version","id":"1656","status":"public"},{"relation":"later_version","id":"467","status":"public"}]},"_id":"5436","type":"technical_report","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","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","last_name":"Henzinger","first_name":"Thomas A"},{"last_name":"Otop","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"IST Austria","date_updated":"2026-07-07T14:01:10Z","title":"Nested weighted automata","language":[{"iso":"eng"}],"month":"04","date_published":"2015-04-24T00:00:00Z","oa":1,"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"}],"publication_status":"published","file_date_updated":"2020-07-14T12:46:54Z","page":"29","day":"24","pubrep_id":"331","status":"public","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2015-170-v2-2","publication_identifier":{"issn":["2664-1690"]},"year":"2015","date_created":"2018-12-12T11:39:19Z","ddc":["000"],"has_accepted_license":"1","file":[{"file_size":569991,"date_updated":"2020-07-14T12:46:54Z","access_level":"open_access","checksum":"3c402f47d3669c28d04d1af405a08e3f","relation":"main_file","file_id":"5541","creator":"system","file_name":"IST-2015-170-v2+2_report.pdf","content_type":"application/pdf","date_created":"2018-12-12T11:54:19Z"}],"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>.","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>.","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>","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2015.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015."}}]