[{"oa":1,"type":"technical_report","page":"33","related_material":{"record":[{"id":"5412","relation":"earlier_version","status":"public"},{"relation":"earlier_version","id":"5413","status":"public"},{"status":"public","id":"2063","relation":"later_version"}]},"file_date_updated":"2020-07-14T12:46:48Z","publication_identifier":{"issn":["2664-1690"]},"day":"07","date_published":"2014-02-07T00:00:00Z","date_updated":"2025-04-15T07:56:48Z","title":"CEGAR for qualitative analysis of probabilistic systems","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_id":"5464","date_updated":"2020-07-14T12:46:48Z","checksum":"87b93fe9af71fc5c94b0eb6151537e11","creator":"system","file_name":"IST-2014-153-v3+1_main.pdf","relation":"main_file","date_created":"2018-12-12T11:53:03Z","content_type":"application/pdf","access_level":"open_access","file_size":606227}],"author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","first_name":"Przemyslaw","last_name":"Daca"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"}],"year":"2014","publication_status":"published","citation":{"short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>."},"doi":"10.15479/AT:IST-2014-153-v3-1","language":[{"iso":"eng"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. ","lang":"eng"}],"has_accepted_license":"1","date_created":"2018-12-12T11:39:12Z","department":[{"_id":"KrCh"}],"ddc":["000"],"status":"public","oa_version":"Published Version","month":"02","_id":"5414","pubrep_id":"165"},{"oa":1,"type":"technical_report","page":"18","publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:49Z","related_material":{"record":[{"relation":"later_version","id":"2163","status":"public"}]},"day":"22","date_updated":"2025-04-15T07:55:59Z","date_published":"2014-03-22T00:00:00Z","title":"Games with a weak adversary","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_updated":"2020-07-14T12:46:49Z","file_id":"5468","content_type":"application/pdf","access_level":"open_access","file_size":328253,"file_name":"IST-2014-176-v1+1_icalp_14.pdf","creator":"system","checksum":"1d6958aa60050e1c3e932c6e5f34c39f","relation":"main_file","date_created":"2018-12-12T11:53:07Z"}],"author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"}],"year":"2014","publication_status":"published","doi":"10.15479/AT:IST-2014-176-v1-1","citation":{"mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>.","ieee":"K. Chatterjee and L. Doyen, <i>Games with a weak adversary</i>. IST Austria, 2014.","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.","apa":"Chatterjee, K., &#38; Doyen, L. (2014). <i>Games with a weak adversary</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>","ama":"Chatterjee K, Doyen L. <i>Games with a Weak Adversary</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">10.15479/AT:IST-2014-176-v1-1</a>","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Games with a Weak Adversary</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-176-v1-1\">https://doi.org/10.15479/AT:IST-2014-176-v1-1</a>.","short":"K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014."},"language":[{"iso":"eng"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results."}],"date_created":"2018-12-12T11:39:13Z","has_accepted_license":"1","department":[{"_id":"KrCh"}],"status":"public","ddc":["000","005"],"oa_version":"Published Version","month":"03","_id":"5418","pubrep_id":"176"},{"pubrep_id":"187","_id":"5419","month":"04","status":"public","oa_version":"Published Version","ddc":["000"],"abstract":[{"text":"We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:\r\n1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).\r\n2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.\r\nOur algorithms improve all existing results, and use very simple data structures.","lang":"eng"}],"has_accepted_license":"1","date_created":"2018-12-12T11:39:13Z","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2014-187-v1-1","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Improved algorithms for reachability and shortest path on low tree-width graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">10.15479/AT:IST-2014-187-v1-1</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-187-v1-1\">https://doi.org/10.15479/AT:IST-2014-187-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014."},"publication_status":"published","year":"2014","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","first_name":"Andreas"}],"file":[{"date_created":"2018-12-12T11:54:25Z","relation":"main_file","creator":"system","file_name":"IST-2014-187-v1+1_main_full_tech.pdf","checksum":"c608e66030a4bf51d2d99b451f539b99","file_size":670031,"access_level":"open_access","content_type":"application/pdf","file_id":"5548","date_updated":"2020-07-14T12:46:50Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Improved algorithms for reachability and shortest path on low tree-width graphs","date_published":"2014-04-14T00:00:00Z","date_updated":"2021-01-12T08:02:03Z","day":"14","publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:50Z","page":"34","type":"technical_report","oa":1},{"publication_status":"published","year":"2014","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"file":[{"file_id":"5520","date_updated":"2020-07-14T12:46:50Z","date_created":"2018-12-12T11:53:58Z","relation":"main_file","file_name":"IST-2014-191-v1+1_main_full.pdf","creator":"system","checksum":"49e0fd3e62650346daf7dc04604f7a0a","file_size":584368,"access_level":"open_access","content_type":"application/pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"The value 1 problem for concurrent mean-payoff games","date_updated":"2021-01-12T08:02:05Z","date_published":"2014-04-14T00:00:00Z","day":"14","file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"page":"49","type":"technical_report","oa":1,"pubrep_id":"191","_id":"5420","status":"public","month":"04","oa_version":"Published Version","ddc":["000","005"],"has_accepted_license":"1","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"}],"date_created":"2018-12-12T11:39:14Z","department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","language":[{"iso":"eng"}],"citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>.","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2014). <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">https://doi.org/10.15479/AT:IST-2014-191-v1-1</a>","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Value 1 Problem for Concurrent Mean-Payoff Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-191-v1-1\">10.15479/AT:IST-2014-191-v1-1</a>.","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The value 1 problem for concurrent mean-payoff games</i>. IST Austria, 2014."},"doi":"10.15479/AT:IST-2014-191-v1-1"},{"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_published":"2014-04-18T00:00:00Z","date_updated":"2023-02-23T12:26:33Z","title":"The complexity of evolution on graphs","year":"2014","publication_status":"published","file":[{"file_id":"5538","date_updated":"2020-07-14T12:46:50Z","relation":"main_file","date_created":"2018-12-12T11:54:16Z","creator":"system","file_name":"IST-2014-190-v2+2_main_full.pdf","checksum":"42f3d8b563286eb0d903832bd9a848d3","file_size":443529,"content_type":"application/pdf","access_level":"open_access"},{"file_id":"6852","date_updated":"2020-07-14T12:46:50Z","date_created":"2019-09-06T07:30:20Z","relation":"main_file","creator":"kschuh","file_name":"IST-2014-190-v1+1_main_full.pdf","checksum":"0c9a2fd822309719634495a35957e34d","file_size":440911,"access_level":"open_access","content_type":"application/pdf"}],"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"type":"technical_report","oa":1,"related_material":{"record":[{"relation":"later_version","id":"5432","status":"public"},{"id":"5440","relation":"later_version","status":"public"}]},"file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"day":"18","page":"27","_id":"5421","status":"public","ddc":["000","005"],"oa_version":"Published Version","month":"04","pubrep_id":"190","language":[{"iso":"eng"}],"citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on Graphs, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2014). <i>The complexity of evolution on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">https://doi.org/10.15479/AT:IST-2014-190-v2-2</a>","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on graphs, IST Austria, 27p.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolution on Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolution on graphs</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolution on Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-190-v2-2\">10.15479/AT:IST-2014-190-v2-2</a>."},"doi":"10.15479/AT:IST-2014-190-v2-2","alternative_title":["IST Austria Technical Report"],"date_created":"2018-12-12T11:39:14Z","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time."}],"has_accepted_license":"1","publisher":"IST Austria"},{"oa_version":"Published Version","status":"public","month":"07","ddc":["005"],"_id":"5423","pubrep_id":"300","doi":"10.15479/AT:IST-2014-300-v1-1","citation":{"short":"K. Chatterjee, A. Kössler, A. Pavlogiannis, U. Schmid, A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Alexander Kössler, Andreas Pavlogiannis, and Ulrich Schmid. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>.","ista":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. 2014. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks, IST Austria, 14p.","apa":"Chatterjee, K., Kössler, A., Pavlogiannis, A., &#38; Schmid, U. (2014). <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">https://doi.org/10.15479/AT:IST-2014-300-v1-1</a>","ama":"Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>","ieee":"K. Chatterjee, A. Kössler, A. Pavlogiannis, and U. Schmid, <i>A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-300-v1-1\">10.15479/AT:IST-2014-300-v1-1</a>."},"language":[{"iso":"eng"}],"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","date_created":"2018-12-12T11:39:15Z","abstract":[{"text":"We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. ","lang":"eng"}],"department":[{"_id":"KrCh"}],"date_updated":"2025-09-29T13:15:35Z","date_published":"2014-07-29T00:00:00Z","title":"A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"relation":"main_file","date_created":"2018-12-12T11:53:53Z","file_name":"IST-2014-300-v1+1_main.pdf","creator":"system","checksum":"4b8fde4d9ef6653837f6803921d83032","file_size":1270021,"content_type":"application/pdf","access_level":"open_access","file_id":"5514","date_updated":"2020-07-14T12:46:50Z"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Kössler, Alexander","last_name":"Kössler","first_name":"Alexander"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","first_name":"Andreas"},{"last_name":"Schmid","first_name":"Ulrich","full_name":"Schmid, Ulrich"}],"year":"2014","publication_status":"published","oa":1,"type":"technical_report","page":"14","file_date_updated":"2020-07-14T12:46:50Z","publication_identifier":{"issn":["2664-1690"]},"related_material":{"record":[{"status":"public","relation":"later_version","id":"1714"}]},"day":"29"},{"day":"09","publication_identifier":{"issn":["2664-1690"]},"related_material":{"record":[{"status":"public","relation":"later_version","id":"5426"},{"status":"public","id":"1732","relation":"later_version"}]},"file_date_updated":"2020-07-14T12:46:51Z","page":"12","type":"technical_report","oa":1,"publication_status":"published","year":"2014","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gupta, Raghav","first_name":"Raghav","last_name":"Gupta"},{"first_name":"Ayush","last_name":"Kanodia","full_name":"Kanodia, Ayush"}],"file":[{"date_updated":"2020-07-14T12:46:51Z","file_id":"5512","file_size":655774,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:51Z","file_name":"IST-2014-305-v1+1_main.pdf","creator":"system","checksum":"35009d5fad01198341e6c1a3353481b7"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","date_updated":"2025-04-15T07:55:41Z","date_published":"2014-09-09T00:00:00Z","date_created":"2018-12-12T11:39:15Z","has_accepted_license":"1","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."}],"department":[{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","language":[{"iso":"eng"}],"citation":{"apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2014). <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">https://doi.org/10.15479/AT:IST-2014-305-v1-1</a>","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">10.15479/AT:IST-2014-305-v1-1</a>","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 12p.","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">10.15479/AT:IST-2014-305-v1-1</a>.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v1-1\">https://doi.org/10.15479/AT:IST-2014-305-v1-1</a>."},"doi":"10.15479/AT:IST-2014-305-v1-1","pubrep_id":"305","_id":"5424","oa_version":"Published Version","status":"public","ddc":["005"],"month":"09"},{"page":"10","publication_identifier":{"issn":["2664-1690"]},"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5424"},{"status":"public","id":"1732","relation":"later_version"}]},"file_date_updated":"2020-07-14T12:46:51Z","day":"29","oa":1,"type":"technical_report","file":[{"access_level":"open_access","content_type":"application/pdf","file_size":656019,"checksum":"730c0a8e97cf2712a884b2cc423f3919","file_name":"IST-2014-305-v2+1_main2.pdf","creator":"system","date_created":"2018-12-12T11:54:15Z","relation":"main_file","date_updated":"2020-07-14T12:46:51Z","file_id":"5537"}],"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"},{"last_name":"Gupta","first_name":"Raghav","full_name":"Gupta, Raghav"},{"full_name":"Kanodia, Ayush","last_name":"Kanodia","first_name":"Ayush"}],"year":"2014","publication_status":"published","date_updated":"2025-04-15T07:55:41Z","date_published":"2014-09-29T00:00:00Z","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.","lang":"eng"}],"has_accepted_license":"1","date_created":"2018-12-12T11:39:16Z","department":[{"_id":"KrCh"}],"doi":"10.15479/AT:IST-2014-305-v2-1","citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014.","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">10.15479/AT:IST-2014-305-v2-1</a>.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 10p.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2014). <i>Qualitative analysis of POMDPs with temporal logic specifications for robotics applications</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-305-v2-1\">10.15479/AT:IST-2014-305-v2-1</a>"},"language":[{"iso":"eng"}],"pubrep_id":"311","status":"public","oa_version":"Published Version","ddc":["005"],"month":"09","_id":"5426"},{"author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"file":[{"file_id":"5471","date_updated":"2020-07-14T12:46:52Z","checksum":"9d3b90bf4fff74664f182f2d95ef727a","creator":"system","file_name":"IST-2014-314-v1+1_long.pdf","date_created":"2018-12-12T11:53:10Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":405561}],"publication_status":"published","year":"2014","title":"Optimal tree-decomposition balancing and reachability on low treewidth graphs","date_updated":"2021-01-12T08:02:09Z","date_published":"2014-11-05T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"24","day":"05","file_date_updated":"2020-07-14T12:46:52Z","publication_identifier":{"issn":["2664-1690"]},"oa":1,"type":"technical_report","pubrep_id":"314","oa_version":"Published Version","month":"11","status":"public","ddc":["000"],"_id":"5427","publisher":"IST Austria","date_created":"2018-12-12T11:39:16Z","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries."}],"has_accepted_license":"1","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2014-314-v1-1","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2014). <i>Optimal tree-decomposition balancing and reachability on low treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">https://doi.org/10.15479/AT:IST-2014-314-v1-1</a>","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">10.15479/AT:IST-2014-314-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition balancing and reachability on low treewidth graphs, IST Austria, 24p.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Optimal tree-decomposition balancing and reachability on low treewidth graphs</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">10.15479/AT:IST-2014-314-v1-1</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs, IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-314-v1-1\">https://doi.org/10.15479/AT:IST-2014-314-v1-1</a>."},"language":[{"iso":"eng"}]},{"type":"technical_report","oa":1,"day":"05","related_material":{"record":[{"id":"1066","relation":"later_version","status":"public"}]},"publication_identifier":{"issn":["2664-1690"]},"file_date_updated":"2020-07-14T12:46:52Z","page":"26","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Quantitative fair simulation games","date_published":"2014-12-05T00:00:00Z","date_updated":"2026-06-18T08:47:00Z","publication_status":"published","year":"2014","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"},{"last_name":"Velner","first_name":"Yaron","full_name":"Velner, Yaron"}],"file":[{"file_id":"5521","date_updated":"2020-07-14T12:46:52Z","checksum":"b1d573bc04365625ff9974880c0aa807","file_name":"IST-2014-315-v1+1_report.pdf","creator":"system","relation":"main_file","date_created":"2018-12-12T11:53:59Z","content_type":"application/pdf","access_level":"open_access","file_size":531046}],"language":[{"iso":"eng"}],"citation":{"ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, <i>Quantitative fair simulation games</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Quantitative Fair Simulation Games</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">10.15479/AT:IST-2014-315-v1-1</a>.","apa":"Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Velner, Y. (2014). <i>Quantitative fair simulation games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>","ama":"Chatterjee K, Henzinger TA, Otop J, Velner Y. <i>Quantitative Fair Simulation Games</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">10.15479/AT:IST-2014-315-v1-1</a>","ista":"Chatterjee K, Henzinger TA, Otop J, Velner Y. 2014. Quantitative fair simulation games, IST Austria, 26p.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Yaron Velner. <i>Quantitative Fair Simulation Games</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-315-v1-1\">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Quantitative Fair Simulation Games, IST Austria, 2014."},"doi":"10.15479/AT:IST-2014-315-v1-1","abstract":[{"lang":"eng","text":"Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms.\r\n\r\nIn this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata."}],"date_created":"2018-12-12T11:39:16Z","has_accepted_license":"1","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","_id":"5428","month":"12","status":"public","ddc":["004"],"oa_version":"Published Version","pubrep_id":"315"},{"publisher":"Public Library of Science","has_accepted_license":"1","abstract":[{"lang":"eng","text":"A fundamental question in biology is the following: what is the time scale that is needed for evolutionary innovations? There are many results that characterize single steps in terms of the fixation time of new mutants arising in populations of certain size and structure. But here we ask a different question, which is concerned with the much longer time scale of evolutionary trajectories: how long does it take for a population exploring a fitness landscape to find target sequences that encode new biological functions? Our key variable is the length, (Formula presented.) of the genetic sequence that undergoes adaptation. In computer science there is a crucial distinction between problems that require algorithms which take polynomial or exponential time. The latter are considered to be intractable. Here we develop a theoretical approach that allows us to estimate the time of evolution as function of (Formula presented.) We show that adaptation on many fitness landscapes takes time that is exponential in (Formula presented.) even if there are broad selection gradients and many targets uniformly distributed in sequence space. These negative results lead us to search for specific mechanisms that allow evolution to work on polynomial time scales. We study a regeneration process and show that it enables evolution to work in polynomial time."}],"date_created":"2018-12-11T11:55:22Z","intvolume":"        10","language":[{"iso":"eng"}],"issue":"9","status":"public","month":"09","ddc":["510"],"corr_author":"1","publication":"PLoS Computational Biology","oa":1,"ec_funded":1,"type":"journal_article","isi":1,"file":[{"date_created":"2018-12-12T10:11:35Z","relation":"main_file","creator":"system","file_name":"IST-2016-440-v1+1_journal.pcbi.1003818.pdf","checksum":"712d4c5787ddf97809cfc962507f0738","file_size":1399093,"access_level":"open_access","content_type":"application/pdf","file_id":"4890","date_updated":"2020-07-14T12:45:26Z"}],"publication_status":"published","article_processing_charge":"No","year":"2014","article_number":"7p","date_published":"2014-09-11T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":10,"department":[{"_id":"KrCh"}],"scopus_import":"1","doi":"10.1371/journal.pcbi.1003818","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"mla":"Chatterjee, Krishnendu, et al. “The Time Scale of Evolutionary Innovation.” <i>PLoS Computational Biology</i>, vol. 10, no. 9, 7p, Public Library of Science, 2014, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003818\">10.1371/journal.pcbi.1003818</a>.","ieee":"K. Chatterjee, A. Pavlogiannis, B. Adlam, and M. Nowak, “The time scale of evolutionary innovation,” <i>PLoS Computational Biology</i>, vol. 10, no. 9. Public Library of Science, 2014.","apa":"Chatterjee, K., Pavlogiannis, A., Adlam, B., &#38; Nowak, M. (2014). The time scale of evolutionary innovation. <i>PLoS Computational Biology</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1003818\">https://doi.org/10.1371/journal.pcbi.1003818</a>","ista":"Chatterjee K, Pavlogiannis A, Adlam B, Nowak M. 2014. The time scale of evolutionary innovation. PLoS Computational Biology. 10(9), 7p.","ama":"Chatterjee K, Pavlogiannis A, Adlam B, Nowak M. The time scale of evolutionary innovation. <i>PLoS Computational Biology</i>. 2014;10(9). doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003818\">10.1371/journal.pcbi.1003818</a>","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, Ben Adlam, and Martin Nowak. “The Time Scale of Evolutionary Innovation.” <i>PLoS Computational Biology</i>. Public Library of Science, 2014. <a href=\"https://doi.org/10.1371/journal.pcbi.1003818\">https://doi.org/10.1371/journal.pcbi.1003818</a>.","short":"K. Chatterjee, A. Pavlogiannis, B. Adlam, M. Nowak, PLoS Computational Biology 10 (2014)."},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"pubrep_id":"440","quality_controlled":"1","oa_version":"Published Version","_id":"2039","publist_id":"5012","day":"11","related_material":{"record":[{"relation":"research_data","id":"9739","status":"public"}]},"file_date_updated":"2020-07-14T12:45:26Z","external_id":{"isi":["000343011700018"]},"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis"},{"first_name":"Ben","last_name":"Adlam","full_name":"Adlam, Ben"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"title":"The time scale of evolutionary innovation","date_updated":"2025-09-29T11:53:46Z"},{"intvolume":"      8704","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LNCS"],"abstract":[{"text":"A standard technique for solving the parameterized model checking problem is to reduce it to the classic model checking problem of finitely many finite-state systems. This work considers some of the theoretical power and limitations of this technique. We focus on concurrent systems in which processes communicate via pairwise rendezvous, as well as the special cases of disjunctive guards and token passing; specifications are expressed in indexed temporal logic without the next operator; and the underlying network topologies are generated by suitable Monadic Second Order Logic formulas and graph operations. First, we settle the exact computational complexity of the parameterized model checking problem for some of our concurrent systems, and establish new decidability results for others. Second, we consider the cases that model checking the parameterized system can be reduced to model checking some fixed number of processes, the number is known as a cutoff. We provide many cases for when such cutoffs can be computed, establish lower bounds on the size of such cutoffs, and identify cases where no cutoff exists. Third, we consider cases for which the parameterized system is equivalent to a single finite-state system (more precisely a Büchi word automaton), and establish tight bounds on the sizes of such automata.","lang":"eng"}],"date_created":"2018-12-11T11:55:26Z","month":"09","status":"public","publication":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","type":"conference","page":"109 - 124","editor":[{"last_name":"Baldan","first_name":"Paolo","full_name":"Baldan, Paolo"},{"full_name":"Gorla, Daniele","first_name":"Daniele","last_name":"Gorla"}],"date_published":"2014-09-01T00:00:00Z","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","year":"2014","publication_status":"published","doi":"10.1007/978-3-662-44584-6_9","citation":{"ieee":"B. Aminof, T. Kotek, S. Rubin, F. Spegni, and H. Veith, “Parameterized model checking of rendezvous systems,” in <i>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, Rome, Italy, 2014, vol. 8704, pp. 109–124.","mla":"Aminof, Benjamin, et al. “Parameterized Model Checking of Rendezvous Systems.” <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, edited by Paolo Baldan and Daniele Gorla, vol. 8704, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 109–24, doi:<a href=\"https://doi.org/10.1007/978-3-662-44584-6_9\">10.1007/978-3-662-44584-6_9</a>.","ista":"Aminof B, Kotek T, Rubin S, Spegni F, Veith H. 2014. Parameterized model checking of rendezvous systems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). CONCUR: Concurrency Theory, LNCS, vol. 8704, 109–124.","ama":"Aminof B, Kotek T, Rubin S, Spegni F, Veith H. Parameterized model checking of rendezvous systems. In: Baldan P, Gorla D, eds. <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>. Vol 8704. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2014:109-124. doi:<a href=\"https://doi.org/10.1007/978-3-662-44584-6_9\">10.1007/978-3-662-44584-6_9</a>","apa":"Aminof, B., Kotek, T., Rubin, S., Spegni, F., &#38; Veith, H. (2014). Parameterized model checking of rendezvous systems. In P. Baldan &#38; D. Gorla (Eds.), <i>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i> (Vol. 8704, pp. 109–124). Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.1007/978-3-662-44584-6_9\">https://doi.org/10.1007/978-3-662-44584-6_9</a>","chicago":"Aminof, Benjamin, Tomer Kotek, Sacha Rubin, Francesco Spegni, and Helmut Veith. “Parameterized Model Checking of Rendezvous Systems.” In <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, edited by Paolo Baldan and Daniele Gorla, 8704:109–24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. <a href=\"https://doi.org/10.1007/978-3-662-44584-6_9\">https://doi.org/10.1007/978-3-662-44584-6_9</a>.","short":"B. Aminof, T. Kotek, S. Rubin, F. Spegni, H. Veith, in:, P. Baldan, D. Gorla (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 109–124."},"volume":8704,"department":[{"_id":"KrCh"}],"scopus_import":"1","oa_version":"None","quality_controlled":"1","publist_id":"4994","_id":"2052","conference":{"end_date":"2014-09-05","start_date":"2014-09-02","name":"CONCUR: Concurrency Theory","location":"Rome, Italy"},"acknowledgement":"The second, third, fourth and fifth authors were supported by the Austrian National Research Network S11403-N23 (RiSE) of the Austrian Science Fund (FWF) and by the Vienna Science and Technology Fund (WWTF) through grants PROSEED, ICT12-059, and VRG11-005.","day":"01","date_updated":"2024-10-21T06:02:50Z","title":"Parameterized model checking of rendezvous systems","author":[{"id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","full_name":"Aminof, Benjamin","last_name":"Aminof","first_name":"Benjamin"},{"full_name":"Kotek, Tomer","first_name":"Tomer","last_name":"Kotek"},{"last_name":"Rubin","first_name":"Sacha","full_name":"Rubin, Sacha"},{"first_name":"Francesco","last_name":"Spegni","full_name":"Spegni, Francesco"},{"full_name":"Veith, Helmut","first_name":"Helmut","last_name":"Veith"}]},{"arxiv":1,"day":"01","acknowledgement":"This work is supported by the EU 7th Framework Programme under grant agreements 295261 (MEALS) and 318490 (SENSATION), Czech Science Foundation under grant agreement P202/12/G061, the DFG Transregional Collaborative Research Centre SFB/TR 14 AVACS, and by the CAS/SAFEA International Partnership Program for Creative Research Teams.","external_id":{"arxiv":["1404.5084"]},"conference":{"end_date":"2014-09-05","name":"CONCUR: Concurrency Theory","location":"Rome, Italy","start_date":"2014-09-02"},"author":[{"last_name":"Hermanns","first_name":"Holger","full_name":"Hermanns, Holger"},{"full_name":"Krčál, Jan","last_name":"Krčál","first_name":"Jan"},{"orcid":"0000-0002-8122-2881","last_name":"Kretinsky","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"}],"title":"Probabilistic bisimulation: Naturally on distributions","date_updated":"2025-06-11T07:57:15Z","volume":8704,"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"scopus_import":"1","doi":"10.1007/978-3-662-44584-6_18","citation":{"ieee":"H. Hermanns, J. Krčál, and J. Kretinsky, “Probabilistic bisimulation: Naturally on distributions,” in <i>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, Rome, Italy, 2014, vol. 8704, pp. 249–265.","mla":"Hermanns, Holger, et al. “Probabilistic Bisimulation: Naturally on Distributions.” <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, edited by Paolo Baldan and Daniele Gorla, vol. 8704, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 249–65, doi:<a href=\"https://doi.org/10.1007/978-3-662-44584-6_18\">10.1007/978-3-662-44584-6_18</a>.","ama":"Hermanns H, Krčál J, Kretinsky J. Probabilistic bisimulation: Naturally on distributions. In: Baldan P, Gorla D, eds. <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>. Vol 8704. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2014:249-265. doi:<a href=\"https://doi.org/10.1007/978-3-662-44584-6_18\">10.1007/978-3-662-44584-6_18</a>","ista":"Hermanns H, Krčál J, Kretinsky J. 2014. Probabilistic bisimulation: Naturally on distributions. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). CONCUR: Concurrency Theory, LNCS, vol. 8704, 249–265.","apa":"Hermanns, H., Krčál, J., &#38; Kretinsky, J. (2014). Probabilistic bisimulation: Naturally on distributions. In P. Baldan &#38; D. Gorla (Eds.), <i>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i> (Vol. 8704, pp. 249–265). Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.1007/978-3-662-44584-6_18\">https://doi.org/10.1007/978-3-662-44584-6_18</a>","chicago":"Hermanns, Holger, Jan Krčál, and Jan Kretinsky. “Probabilistic Bisimulation: Naturally on Distributions.” In <i>Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</i>, edited by Paolo Baldan and Daniele Gorla, 8704:249–65. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. <a href=\"https://doi.org/10.1007/978-3-662-44584-6_18\">https://doi.org/10.1007/978-3-662-44584-6_18</a>.","short":"H. Hermanns, J. Krčál, J. Kretinsky, in:, P. Baldan, D. Gorla (Eds.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 249–265."},"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","call_identifier":"FWF","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"}],"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1404.5084"}],"_id":"2053","publist_id":"4993","editor":[{"last_name":"Baldan","first_name":"Paolo","full_name":"Baldan, Paolo"},{"full_name":"Gorla, Daniele","first_name":"Daniele","last_name":"Gorla"}],"page":"249 - 265","oa":1,"type":"conference","ec_funded":1,"publication_status":"published","year":"2014","article_processing_charge":"No","date_published":"2014-09-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2018-12-11T11:55:27Z","abstract":[{"lang":"eng","text":"In contrast to the usual understanding of probabilistic systems as stochastic processes, recently these systems have also been regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as to systems with uncountable state and action spaces. Several examples demonstrate that our definition refines the understanding of behavioural equivalences of probabilistic systems. In particular, it solves a longstanding open problem concerning the representation of memoryless continuous time by memoryfull continuous time. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of uncountably infinite systems."}],"alternative_title":["LNCS"],"intvolume":"      8704","language":[{"iso":"eng"}],"status":"public","publication":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","month":"09"},{"status":"public","month":"07","corr_author":"1","language":[{"iso":"eng"}],"intvolume":"      8559","alternative_title":["LNCS"],"date_created":"2018-12-11T11:55:30Z","abstract":[{"text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems.We focus on qualitative properties forMDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation ofMDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.We present an automated technique for assume-guarantee style reasoning for compositional analysis ofMDPs with qualitative properties by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements.","lang":"eng"}],"publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2014-07-01T00:00:00Z","year":"2014","publication_status":"published","ec_funded":1,"type":"conference","page":"473 - 490","publist_id":"4978","_id":"2063","quality_controlled":"1","oa_version":"None","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"}],"doi":"10.1007/978-3-319-08867-9_31","citation":{"short":"K. Chatterjee, M. Chmelik, P. Daca, in:, Springer, 2014, pp. 473–490.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Przemyslaw Daca. “CEGAR for Qualitative Analysis of Probabilistic Systems,” 8559:473–90. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">https://doi.org/10.1007/978-3-319-08867-9_31</a>.","ama":"Chatterjee K, Chmelik M, Daca P. CEGAR for qualitative analysis of probabilistic systems. In: Vol 8559. Springer; 2014:473-490. doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">10.1007/978-3-319-08867-9_31</a>","apa":"Chatterjee, K., Chmelik, M., &#38; Daca, P. (2014). CEGAR for qualitative analysis of probabilistic systems (Vol. 8559, pp. 473–490). Presented at the CAV: Computer Aided Verification, Vienna, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">https://doi.org/10.1007/978-3-319-08867-9_31</a>","ista":"Chatterjee K, Chmelik M, Daca P. 2014. CEGAR for qualitative analysis of probabilistic systems. CAV: Computer Aided Verification, LNCS, vol. 8559, 473–490.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. Vol. 8559, Springer, 2014, pp. 473–90, doi:<a href=\"https://doi.org/10.1007/978-3-319-08867-9_31\">10.1007/978-3-319-08867-9_31</a>.","ieee":"K. Chatterjee, M. Chmelik, and P. Daca, “CEGAR for qualitative analysis of probabilistic systems,” presented at the CAV: Computer Aided Verification, Vienna, Austria, 2014, vol. 8559, pp. 473–490."},"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"scopus_import":"1","volume":8559,"date_updated":"2026-04-15T10:02:12Z","title":"CEGAR for qualitative analysis of probabilistic systems","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"},{"full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","first_name":"Przemyslaw","last_name":"Daca"}],"conference":{"start_date":"2014-07-18","name":"CAV: Computer Aided Verification","location":"Vienna, Austria","end_date":"2014-07-22"},"related_material":{"record":[{"status":"public","id":"5412","relation":"earlier_version"},{"relation":"earlier_version","id":"5413","status":"public"},{"id":"5414","relation":"earlier_version","status":"public"},{"status":"public","id":"1155","relation":"dissertation_contains"}]},"day":"01"},{"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","date_published":"2014-09-11T00:00:00Z","date_updated":"2025-09-29T11:53:46Z","title":"Detailed proofs for “The time scale of evolutionary innovation”","year":"2014","article_processing_charge":"No","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas"},{"first_name":"Ben","last_name":"Adlam","full_name":"Adlam, Ben"},{"full_name":"Novak, Martin","last_name":"Novak","first_name":"Martin"}],"type":"research_data_reference","related_material":{"record":[{"status":"public","id":"2039","relation":"used_in_publication"}]},"day":"11","_id":"9739","month":"09","status":"public","oa_version":"Published Version","doi":"10.1371/journal.pcbi.1003818.s001","citation":{"chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, Ben Adlam, and Martin Novak. “Detailed Proofs for ‘The Time Scale of Evolutionary Innovation.’” Public Library of Science, 2014. <a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">https://doi.org/10.1371/journal.pcbi.1003818.s001</a>.","short":"K. Chatterjee, A. Pavlogiannis, B. Adlam, M. Novak, (2014).","ieee":"K. Chatterjee, A. Pavlogiannis, B. Adlam, and M. Novak, “Detailed proofs for ‘The time scale of evolutionary innovation.’” Public Library of Science, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Detailed Proofs for “The Time Scale of Evolutionary Innovation.”</i> Public Library of Science, 2014, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">10.1371/journal.pcbi.1003818.s001</a>.","apa":"Chatterjee, K., Pavlogiannis, A., Adlam, B., &#38; Novak, M. (2014). Detailed proofs for “The time scale of evolutionary innovation.” Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">https://doi.org/10.1371/journal.pcbi.1003818.s001</a>","ista":"Chatterjee K, Pavlogiannis A, Adlam B, Novak M. 2014. Detailed proofs for “The time scale of evolutionary innovation”, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">10.1371/journal.pcbi.1003818.s001</a>.","ama":"Chatterjee K, Pavlogiannis A, Adlam B, Novak M. Detailed proofs for “The time scale of evolutionary innovation.” 2014. doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1003818.s001\">10.1371/journal.pcbi.1003818.s001</a>"},"date_created":"2021-07-28T08:13:57Z","department":[{"_id":"KrCh"}],"publisher":"Public Library of Science"},{"author":[{"full_name":"Cerny, Pavol","first_name":"Pavol","last_name":"Cerny"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"},{"orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"first_name":"Arjun","last_name":"Radhakrishna","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","full_name":"Radhakrishna, Arjun"}],"title":"Interface simulation distances","date_updated":"2025-09-29T13:14:25Z","arxiv":1,"day":"04","related_material":{"record":[{"status":"public","id":"2916","relation":"earlier_version"}]},"external_id":{"isi":["000347601300009"],"arxiv":["1210.2450"]},"oa_version":"Submitted Version","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1210.2450","open_access":"1"}],"_id":"1733","publist_id":"5392","volume":560,"scopus_import":"1","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"doi":"10.1016/j.tcs.2014.08.019","citation":{"ista":"Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. 2014. Interface simulation distances. Theoretical Computer Science. 560(3), 348–363.","apa":"Cerny, P., Chmelik, M., Henzinger, T. A., &#38; Radhakrishna, A. (2014). Interface simulation distances. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2014.08.019\">https://doi.org/10.1016/j.tcs.2014.08.019</a>","ama":"Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. Interface simulation distances. <i>Theoretical Computer Science</i>. 2014;560(3):348-363. doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.08.019\">10.1016/j.tcs.2014.08.019</a>","mla":"Cerny, Pavol, et al. “Interface Simulation Distances.” <i>Theoretical Computer Science</i>, vol. 560, no. 3, Elsevier, 2014, pp. 348–63, doi:<a href=\"https://doi.org/10.1016/j.tcs.2014.08.019\">10.1016/j.tcs.2014.08.019</a>.","ieee":"P. Cerny, M. Chmelik, T. A. Henzinger, and A. Radhakrishna, “Interface simulation distances,” <i>Theoretical Computer Science</i>, vol. 560, no. 3. Elsevier, pp. 348–363, 2014.","short":"P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 560 (2014) 348–363.","chicago":"Cerny, Pavol, Martin Chmelik, Thomas A Henzinger, and Arjun Radhakrishna. “Interface Simulation Distances.” <i>Theoretical Computer Science</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tcs.2014.08.019\">https://doi.org/10.1016/j.tcs.2014.08.019</a>."},"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"publication_status":"published","article_processing_charge":"No","year":"2014","date_published":"2014-12-04T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","page":"348 - 363","oa":1,"type":"journal_article","ec_funded":1,"isi":1,"issue":"3","corr_author":"1","month":"12","status":"public","publication":"Theoretical Computer Science","publisher":"Elsevier","date_created":"2018-12-11T11:53:43Z","abstract":[{"lang":"eng","text":"The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a distance for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intuitively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces, and how to synthesize an interface from incompatible requirements. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies."}],"intvolume":"       560","language":[{"iso":"eng"}]},{"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"doi":"10.2168/LMCS-10(1:13)2014","citation":{"chicago":"Brázdil, Tomáš, Václav Brožek, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Markov Decision Processes with Multiple Long-Run Average Objectives.” <i>Logical Methods in Computer Science</i>. International Federation for Computational Logic, 2014. <a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">https://doi.org/10.2168/LMCS-10(1:13)2014</a>.","short":"T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, Logical Methods in Computer Science 10 (2014).","mla":"Brázdil, Tomáš, et al. “Markov Decision Processes with Multiple Long-Run Average Objectives.” <i>Logical Methods in Computer Science</i>, vol. 10, no. 1, International Federation for Computational Logic, 2014, doi:<a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">10.2168/LMCS-10(1:13)2014</a>.","ieee":"T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, and A. Kučera, “Markov decision processes with multiple long-run average objectives,” <i>Logical Methods in Computer Science</i>, vol. 10, no. 1. International Federation for Computational Logic, 2014.","ista":"Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. 2014. Markov decision processes with multiple long-run average objectives. Logical Methods in Computer Science. 10(1).","apa":"Brázdil, T., Brožek, V., Chatterjee, K., Forejt, V., &#38; Kučera, A. (2014). Markov decision processes with multiple long-run average objectives. <i>Logical Methods in Computer Science</i>. International Federation for Computational Logic. <a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">https://doi.org/10.2168/LMCS-10(1:13)2014</a>","ama":"Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. Markov decision processes with multiple long-run average objectives. <i>Logical Methods in Computer Science</i>. 2014;10(1). doi:<a href=\"https://doi.org/10.2168/LMCS-10(1:13)2014\">10.2168/LMCS-10(1:13)2014</a>"},"department":[{"_id":"KrCh"}],"scopus_import":"1","volume":10,"publist_id":"4727","_id":"2234","oa_version":"Published Version","quality_controlled":"1","pubrep_id":"428","external_id":{"isi":["000333744700001"]},"file_date_updated":"2020-07-14T12:45:34Z","publication_identifier":{"issn":["1860-5974"]},"day":"14","date_updated":"2026-07-06T13:23:35Z","title":"Markov decision processes with multiple long-run average objectives","author":[{"last_name":"Brázdil","first_name":"Tomáš","full_name":"Brázdil, Tomáš"},{"full_name":"Brožek, Václav","last_name":"Brožek","first_name":"Václav"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"full_name":"Forejt, Vojtěch","last_name":"Forejt","first_name":"Vojtěch"},{"full_name":"Kučera, Antonín","first_name":"Antonín","last_name":"Kučera"}],"language":[{"iso":"eng"}],"intvolume":"        10","has_accepted_license":"1","date_created":"2018-12-11T11:56:29Z","abstract":[{"text":"We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with κ limit-average functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the case of one limit-average function, both randomization and memory are necessary for strategies even for ε-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized strategies are sufficient for ε-approximation, for all ε &gt; 0. We further prove that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be ε-approximated in time polynomial in the size of the MDP and 1/ε, and exponential in the number of limit-average functions, for all ε &gt; 0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results.","lang":"eng"}],"publisher":"International Federation for Computational Logic","das_tickbox":"1","status":"public","month":"02","publication":"Logical Methods in Computer Science","ddc":["000"],"issue":"1","ec_funded":1,"type":"journal_article","isi":1,"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2014-02-14T00:00:00Z","article_processing_charge":"No","year":"2014","publication_status":"published","file":[{"date_updated":"2020-07-14T12:45:34Z","file_id":"4656","file_size":375388,"access_level":"open_access","content_type":"application/pdf","date_created":"2018-12-12T10:07:57Z","relation":"main_file","file_name":"IST-2016-428-v1+1_1104.3489.pdf","checksum":"803edcc2d8c1acfba44a9ec43a5eb9f0","creator":"system"}]},{"publication_status":"published","year":"2014","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2014-11-01T00:00:00Z","page":"98 - 114","ec_funded":1,"type":"conference","oa":1,"das_tickbox":"1","publication":"12th International Symposium on Automated Technology for Verification and Analysis","status":"public","month":"11","abstract":[{"lang":"eng","text":"We present a general framework for applying machine-learning algorithms to the verification of Markov decision processes (MDPs). The primary goal of these techniques is to improve performance by avoiding an exhaustive exploration of the state space. Our framework focuses on probabilistic reachability, which is a core property for verification, and is illustrated through two distinct instantiations. The first assumes that full knowledge of the MDP is available, and performs a heuristic-driven partial exploration of the model, yielding precise lower and upper bounds on the required probability. The second tackles the case where we may only sample the MDP, and yields probabilistic guarantees, again in terms of both the lower and upper bounds, which provides efficient stopping criteria for the approximation. The latter is the first extension of statistical model checking for unbounded properties inMDPs. In contrast with other related techniques, our approach is not restricted to time-bounded (finite-horizon) or discounted properties, nor does it assume any particular properties of the MDP. We also show how our methods extend to LTL objectives. We present experimental results showing the performance of our framework on several examples."}],"date_created":"2018-12-11T11:55:17Z","alternative_title":["LNCS"],"publisher":"Springer","language":[{"iso":"eng"}],"intvolume":"      8837","author":[{"full_name":"Brázdil, Tomáš","first_name":"Tomáš","last_name":"Brázdil"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"},{"last_name":"Forejt","first_name":"Vojtěch","full_name":"Forejt, Vojtěch"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","first_name":"Jan","orcid":"0000-0002-8122-2881","last_name":"Kretinsky"},{"first_name":"Marta","last_name":"Kwiatkowska","full_name":"Kwiatkowska, Marta"},{"full_name":"Parker, David","last_name":"Parker","first_name":"David"},{"first_name":"Mateusz","last_name":"Ujma","full_name":"Ujma, Mateusz"}],"title":"Verification of Markov decision processes using learning algorithms","date_updated":"2026-07-07T13:15:34Z","day":"01","acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 246967 (VERIWARE), by the EU FP7 project HIERATIC, by the Czech Science Foundation grant No P202/12/P612, by EPSRC project EP/K038575/1.","arxiv":1,"conference":{"end_date":"2014-11-07","start_date":"2014-11-03","name":"ATVA: Automated Technology for Verification and Analysis","location":"Sydney, Australia"},"external_id":{"arxiv":["1402.2967"]},"_id":"2027","publist_id":"5046","oa_version":"Submitted Version","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1402.2967","open_access":"1"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"scopus_import":"1","volume":8837,"project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"_id":"26241A12-B435-11E9-9278-68D0E5697425","grant_number":"24696","name":"Light-regulated ligand traps for spatio-temporal inhibition of cell signaling"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"citation":{"short":"T. Brázdil, K. Chatterjee, M. Chmelik, V. Forejt, J. Kretinsky, M. Kwiatkowska, D. Parker, M. Ujma, in:, 12th International Symposium on Automated Technology for Verification and Analysis, Springer, 2014, pp. 98–114.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Vojtěch Forejt, Jan Kretinsky, Marta Kwiatkowska, David Parker, and Mateusz Ujma. “Verification of Markov Decision Processes Using Learning Algorithms.” In <i>12th International Symposium on Automated Technology for Verification and Analysis</i>, 8837:98–114. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-319-11936-6_8\">https://doi.org/10.1007/978-3-319-11936-6_8</a>.","apa":"Brázdil, T., Chatterjee, K., Chmelik, M., Forejt, V., Kretinsky, J., Kwiatkowska, M., … Ujma, M. (2014). Verification of Markov decision processes using learning algorithms. In <i>12th International Symposium on Automated Technology for Verification and Analysis</i> (Vol. 8837, pp. 98–114). Sydney, Australia: Springer. <a href=\"https://doi.org/10.1007/978-3-319-11936-6_8\">https://doi.org/10.1007/978-3-319-11936-6_8</a>","ama":"Brázdil T, Chatterjee K, Chmelik M, et al. Verification of Markov decision processes using learning algorithms. In: <i>12th International Symposium on Automated Technology for Verification and Analysis</i>. Vol 8837. Springer; 2014:98-114. doi:<a href=\"https://doi.org/10.1007/978-3-319-11936-6_8\">10.1007/978-3-319-11936-6_8</a>","ista":"Brázdil T, Chatterjee K, Chmelik M, Forejt V, Kretinsky J, Kwiatkowska M, Parker D, Ujma M. 2014. Verification of Markov decision processes using learning algorithms. 12th International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 8837, 98–114.","mla":"Brázdil, Tomáš, et al. “Verification of Markov Decision Processes Using Learning Algorithms.” <i>12th International Symposium on Automated Technology for Verification and Analysis</i>, vol. 8837, Springer, 2014, pp. 98–114, doi:<a href=\"https://doi.org/10.1007/978-3-319-11936-6_8\">10.1007/978-3-319-11936-6_8</a>.","ieee":"T. Brázdil <i>et al.</i>, “Verification of Markov decision processes using learning algorithms,” in <i>12th International Symposium on Automated Technology for Verification and Analysis</i>, Sydney, Australia, 2014, vol. 8837, pp. 98–114."},"doi":"10.1007/978-3-319-11936-6_8"},{"publisher":"IST Austria","has_accepted_license":"1","abstract":[{"lang":"eng","text":"Recently there has been a significant effort to add 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, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.  "}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_created":"2018-12-12T11:39:12Z","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2014-170-v1-1","citation":{"chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2014.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2014.","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria, 27p.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2014). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>"},"language":[{"iso":"eng"}],"pubrep_id":"170","status":"public","month":"02","oa_version":"Published Version","ddc":["004"],"_id":"5415","page":"27","day":"19","file_date_updated":"2020-07-14T12:46:48Z","publication_identifier":{"issn":["2664-1690"]},"related_material":{"record":[{"status":"public","id":"5436","relation":"later_version"},{"status":"public","relation":"later_version","id":"1656"},{"status":"public","relation":"later_version","id":"467"}]},"oa":1,"type":"technical_report","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop"}],"file":[{"file_id":"5497","date_updated":"2020-07-14T12:46:48Z","creator":"system","checksum":"31f90dcf2cf899c3f8c6427cfcc2b3c7","file_name":"IST-2014-170-v1+1_main.pdf","date_created":"2018-12-12T11:53:36Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":573457}],"publication_status":"published","year":"2014","title":"Nested weighted automata","date_published":"2014-02-19T00:00:00Z","date_updated":"2026-07-07T14:01:10Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"pubrep_id":"192","quality_controlled":"1","oa_version":"Submitted Version","_id":"2038","publist_id":"5013","volume":15,"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"scopus_import":"1","doi":"10.1145/2629686","citation":{"chicago":"Boker, Udi, Krishnendu Chatterjee, Thomas A Henzinger, and Orna Kupferman. “Temporal Specifications with Accumulative Values.” <i>ACM Transactions on Computational Logic</i>. ACM, 2014. <a href=\"https://doi.org/10.1145/2629686\">https://doi.org/10.1145/2629686</a>.","short":"U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, ACM Transactions on Computational Logic 15 (2014).","ieee":"U. Boker, K. Chatterjee, T. A. Henzinger, and O. Kupferman, “Temporal specifications with accumulative values,” <i>ACM Transactions on Computational Logic</i>, vol. 15, no. 4. ACM, 2014.","mla":"Boker, Udi, et al. “Temporal Specifications with Accumulative Values.” <i>ACM Transactions on Computational Logic</i>, vol. 15, no. 4, 27, ACM, 2014, doi:<a href=\"https://doi.org/10.1145/2629686\">10.1145/2629686</a>.","ama":"Boker U, Chatterjee K, Henzinger TA, Kupferman O. Temporal specifications with accumulative values. <i>ACM Transactions on Computational Logic</i>. 2014;15(4). doi:<a href=\"https://doi.org/10.1145/2629686\">10.1145/2629686</a>","apa":"Boker, U., Chatterjee, K., Henzinger, T. A., &#38; Kupferman, O. (2014). Temporal specifications with accumulative values. <i>ACM Transactions on Computational Logic</i>. ACM. <a href=\"https://doi.org/10.1145/2629686\">https://doi.org/10.1145/2629686</a>","ista":"Boker U, Chatterjee K, Henzinger TA, Kupferman O. 2014. Temporal specifications with accumulative values. ACM Transactions on Computational Logic. 15(4), 27."},"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Quantitative Reactive Modeling","grant_number":"267989","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"author":[{"id":"31E297B6-F248-11E8-B48F-1D18A9856A87","full_name":"Boker, Udi","first_name":"Udi","last_name":"Boker"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A"},{"first_name":"Orna","last_name":"Kupferman","full_name":"Kupferman, Orna"}],"title":"Temporal specifications with accumulative values","date_updated":"2026-07-07T14:01:43Z","day":"16","article_type":"original","related_material":{"record":[{"id":"5385","relation":"earlier_version","status":"public"},{"status":"public","relation":"earlier_version","id":"3356"}]},"file_date_updated":"2020-07-14T12:45:26Z","acknowledgement":"The research was supported in part by ERC Starting grant 278410 (QUALITY).","external_id":{"isi":["000345570700002"]},"issue":"4","month":"09","publication":"ACM Transactions on Computational Logic","status":"public","ddc":["000","004"],"das_tickbox":"1","publisher":"ACM","abstract":[{"text":"Recently, there has been an effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions. At the heart of quantitative objectives lies the accumulation of values along a computation. It is often the accumulated sum, as with energy objectives, or the accumulated average, as with mean-payoff objectives. We investigate the extension of temporal logics with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric (or Boolean) variable of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the accumulated sum and average of the values of v from the beginning of the computation up to the current point in time. We also allow the path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an entire infinite computation. We study the border of decidability for such quantitative extensions of various temporal logics. In particular, we show that extending the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities with both prefix-accumulation assertions, or extending LTL with both path-accumulation assertions, results in temporal logics whose model-checking problem is decidable. Moreover, the prefix-accumulation assertions may be generalized with &quot;controlled accumulation,&quot; allowing, for example, to specify constraints on the average waiting time between a request and a grant. On the negative side, we show that this branching-time logic is, in a sense, the maximal logic with one or both of the prefix-accumulation assertions that permits a decidable model-checking procedure. Extending a temporal logic that has the EG or EU modalities, such as CTL or LTL, makes the problem undecidable.","lang":"eng"}],"date_created":"2018-12-11T11:55:21Z","has_accepted_license":"1","intvolume":"        15","language":[{"iso":"eng"}],"file":[{"file_id":"4851","date_updated":"2020-07-14T12:45:26Z","checksum":"354c41d37500b56320afce94cf9a99c2","creator":"system","file_name":"IST-2014-192-v1+1_AccumulativeValues.pdf","date_created":"2018-12-12T10:10:59Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":346184}],"publication_status":"published","year":"2014","article_processing_charge":"No","article_number":"27","date_published":"2014-09-16T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"ec_funded":1,"type":"journal_article","isi":1}]