[{"month":"04","title":"Nested weighted automata","date_updated":"2023-02-23T12:25:21Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication_identifier":{"issn":["2664-1690"]},"date_published":"2015-04-24T00:00:00Z","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"full_name":"Otop, Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"year":"2015","page":"29","oa_version":"Published Version","file_date_updated":"2020-07-14T12:46:54Z","pubrep_id":"331","doi":"10.15479/AT:IST-2015-170-v2-2","date_created":"2018-12-12T11:39:19Z","day":"24","publisher":"IST Austria","_id":"5436","language":[{"iso":"eng"}],"status":"public","has_accepted_license":"1","abstract":[{"text":"Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.\r\nIn nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.","lang":"eng"}],"alternative_title":["IST Austria Technical Report"],"publication_status":"published","related_material":{"record":[{"status":"public","relation":"later_version","id":"1656"},{"id":"467","relation":"later_version","status":"public"},{"status":"public","relation":"earlier_version","id":"5415"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"citation":{"ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p.","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">10.15479/AT:IST-2015-170-v2-2</a>.","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">10.15479/AT:IST-2015-170-v2-2</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">https://doi.org/10.15479/AT:IST-2015-170-v2-2</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2015.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2015). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">https://doi.org/10.15479/AT:IST-2015-170-v2-2</a>"},"type":"technical_report","file":[{"access_level":"open_access","file_name":"IST-2015-170-v2+2_report.pdf","date_updated":"2020-07-14T12:46:54Z","content_type":"application/pdf","file_size":569991,"checksum":"3c402f47d3669c28d04d1af405a08e3f","relation":"main_file","creator":"system","date_created":"2018-12-12T11:54:19Z","file_id":"5541"}],"ddc":["000"]},{"ddc":["000"],"type":"technical_report","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015."},"file":[{"file_id":"5473","date_created":"2018-12-12T11:53:12Z","creator":"system","checksum":"f5917c20f84018b362d385c000a2e123","relation":"main_file","file_size":1072137,"content_type":"application/pdf","date_updated":"2020-07-14T12:46:54Z","file_name":"IST-2015-330-v2+1_main.pdf","access_level":"open_access"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1607"},{"id":"5430","relation":"earlier_version","status":"public"}]},"publication_status":"published","alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. \r\nThe algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.\r\nOur main theoretical results are as follows.\r\nFirst, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when the output is $\\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$ and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. "}],"day":"27","date_created":"2018-12-12T11:39:19Z","_id":"5437","publisher":"IST Austria","page":"27","oa_version":"Published Version","doi":"10.15479/AT:IST-2015-330-v2-1","pubrep_id":"333","file_date_updated":"2020-07-14T12:46:54Z","year":"2015","date_published":"2015-04-27T00:00:00Z","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis"}],"month":"04","publication_identifier":{"issn":["2664-1690"]},"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:26:05Z","title":"Faster algorithms for quantitative verification in constant treewidth graphs"},{"ddc":["004"],"file":[{"date_created":"2018-12-12T11:53:56Z","creator":"system","file_id":"5518","file_name":"IST-2015-334-v1+1_report.pdf","access_level":"open_access","checksum":"8a5f2d77560e552af87eb1982437a43b","relation":"main_file","content_type":"application/pdf","date_updated":"2020-07-14T12:46:55Z","file_size":422573}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. <i>Edit Distance for Pushdown Automata</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>.","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, <i>Edit distance for pushdown automata</i>. IST Austria, 2015.","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., &#38; Otop, J. (2015). <i>Edit distance for pushdown automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015."},"type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","text":"The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.\r\nThe problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. "}],"publication_status":"published","related_material":{"record":[{"status":"public","relation":"later_version","id":"1610"},{"id":"465","status":"public","relation":"later_version"}]},"language":[{"iso":"eng"}],"status":"public","has_accepted_license":"1","publisher":"IST Austria","_id":"5438","date_created":"2018-12-12T11:39:20Z","day":"05","pubrep_id":"334","file_date_updated":"2020-07-14T12:46:55Z","doi":"10.15479/AT:IST-2015-334-v1-1","oa_version":"Published Version","page":"15","date_published":"2015-05-05T00:00:00Z","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"year":"2015","date_updated":"2023-02-23T12:20:08Z","title":"Edit distance for pushdown automata","department":[{"_id":"KrCh"}],"publication_identifier":{"issn":["2664-1690"]},"month":"05"},{"date_created":"2018-12-12T11:39:20Z","day":"18","publisher":"IST Austria","_id":"5439","oa_version":"Published Version","page":"20","file_date_updated":"2020-07-14T12:46:55Z","pubrep_id":"335","doi":"10.15479/AT:IST-2015-335-v1-1","date_published":"2015-05-18T00:00:00Z","author":[{"last_name":"Boker","full_name":"Boker, Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","first_name":"Udi"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"year":"2015","month":"05","date_updated":"2023-02-23T10:08:48Z","title":"The target discounted-sum problem","department":[{"_id":"ToHe"}],"publication_identifier":{"issn":["2664-1690"]},"ddc":["004","512","513"],"citation":{"ista":"Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST Austria, 20p.","mla":"Boker, Udi, et al. <i>The Target Discounted-Sum Problem</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">10.15479/AT:IST-2015-335-v1-1</a>.","ama":"Boker U, Henzinger TA, Otop J. <i>The Target Discounted-Sum Problem</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">10.15479/AT:IST-2015-335-v1-1</a>","chicago":"Boker, Udi, Thomas A Henzinger, and Jan Otop. <i>The Target Discounted-Sum Problem</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">https://doi.org/10.15479/AT:IST-2015-335-v1-1</a>.","ieee":"U. Boker, T. A. Henzinger, and J. Otop, <i>The target discounted-sum problem</i>. IST Austria, 2015.","short":"U. Boker, T.A. Henzinger, J. Otop, The Target Discounted-Sum Problem, IST Austria, 2015.","apa":"Boker, U., Henzinger, T. A., &#38; Otop, J. (2015). <i>The target discounted-sum problem</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-335-v1-1\">https://doi.org/10.15479/AT:IST-2015-335-v1-1</a>"},"type":"technical_report","file":[{"creator":"system","date_created":"2018-12-12T11:53:55Z","file_id":"5517","access_level":"open_access","file_name":"IST-2015-335-v1+1_report.pdf","file_size":589619,"date_updated":"2020-07-14T12:46:55Z","content_type":"application/pdf","checksum":"40405907aa012acece1bc26cf0be554d","relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","alternative_title":["IST Austria Technical Report"],"publication_status":"published","abstract":[{"text":"The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata. ","lang":"eng"}],"related_material":{"record":[{"id":"1659","status":"public","relation":"later_version"}]}},{"year":"2015","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"date_published":"2015-06-16T00:00:00Z","month":"06","publication_identifier":{"issn":["2664-1690"]},"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:26:10Z","title":"The complexity of evolutionary games on graphs","day":"16","date_created":"2018-12-12T11:39:21Z","publisher":"IST Austria","_id":"5440","page":"18","oa_version":"Published Version","doi":"10.15479/AT:IST-2015-323-v2-2","pubrep_id":"338","file_date_updated":"2020-07-14T12:46:56Z","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","status":"public","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5421"},{"relation":"earlier_version","status":"public","id":"5432"}]},"publication_status":"published","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.","lang":"eng"}],"ddc":["005","576"],"type":"technical_report","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity of evolutionary games on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v2-2\">10.15479/AT:IST-2015-323-v2-2</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p."},"file":[{"file_id":"5484","date_created":"2018-12-12T11:53:23Z","creator":"system","file_size":466161,"date_updated":"2020-07-14T12:46:56Z","content_type":"application/pdf","checksum":"66aace7d367032af97c15e35c9be9636","relation":"main_file","access_level":"open_access","file_name":"IST-2015-323-v2+2_main.pdf"}]},{"file_date_updated":"2020-07-14T12:46:56Z","pubrep_id":"340","doi":"10.15479/AT:IST-2015-340-v1-1","oa_version":"Published Version","page":"24","_id":"5441","publisher":"IST Austria","date_created":"2018-12-12T11:39:21Z","day":"11","title":"Algorithms for algebraic path properties in concurrent systems of constant treewidth components","date_updated":"2023-09-19T14:36:19Z","department":[{"_id":"KrCh"}],"publication_identifier":{"issn":["2664-1690"]},"month":"07","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir","last_name":"Goharshady"},{"last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2015-07-11T00:00:00Z","year":"2015","file":[{"date_updated":"2020-07-14T12:46:56Z","content_type":"application/pdf","file_size":861396,"relation":"main_file","checksum":"df383dc62c94d7b2ea639aba088a76c6","access_level":"open_access","file_name":"IST-2015-340-v1+1_main.pdf","file_id":"5531","creator":"system","date_created":"2018-12-12T11:54:09Z"}],"type":"technical_report","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., &#38; Pavlogiannis, A. (2015). <i>Algorithms for algebraic path properties in concurrent systems of constant treewidth components</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 24p.","mla":"Chatterjee, Krishnendu, et al. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">https://doi.org/10.15479/AT:IST-2015-340-v1-1</a>.","ama":"Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. <i>Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-340-v1-1\">10.15479/AT:IST-2015-340-v1-1</a>"},"ddc":["000"],"alternative_title":["IST Austria Technical Report"],"publication_status":"published","abstract":[{"lang":"eng","text":"We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks."}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1437"},{"status":"public","relation":"earlier_version","id":"5442"},{"id":"6009","status":"public","relation":"later_version"}]},"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1},{"date_published":"2015-11-06T00:00:00Z","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Chmelik, Martin","last_name":"Chmelik","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin"},{"first_name":"Jessica","id":"378E0060-F248-11E8-B48F-1D18A9856A87","last_name":"Davies","full_name":"Davies, Jessica"}],"year":"2015","date_updated":"2023-02-21T16:24:05Z","title":"A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs","department":[{"_id":"KrCh"}],"publication_identifier":{"issn":["2664-1690"]},"month":"11","_id":"5443","publisher":"IST Austria","date_created":"2018-12-12T11:39:22Z","day":"06","file_date_updated":"2020-07-14T12:46:57Z","pubrep_id":"362","doi":"10.15479/AT:IST-2015-325-v2-1","page":"23","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"abstract":[{"lang":"eng","text":"POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach."}],"alternative_title":["IST Austria Technical Report"],"publication_status":"published","related_material":{"record":[{"id":"1166","relation":"later_version","status":"public"}]},"language":[{"iso":"eng"}],"status":"public","has_accepted_license":"1","ddc":["000"],"file":[{"file_id":"5466","creator":"system","date_created":"2018-12-12T11:53:05Z","content_type":"application/pdf","date_updated":"2020-07-14T12:46:57Z","file_size":412379,"checksum":"f0fa31ad8161ed655137e94012123ef9","relation":"main_file","access_level":"open_access","file_name":"IST-2015-325-v2+1_main.pdf"}],"citation":{"ieee":"K. Chatterjee, M. Chmelik, and J. Davies, <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria, 2015.","short":"K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015.","apa":"Chatterjee, K., Chmelik, M., &#38; Davies, J. (2015). <i>A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>","ista":"Chatterjee K, Chmelik M, Davies J. 2015. A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs, IST Austria, 23p.","mla":"Chatterjee, Krishnendu, et al. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>.","ama":"Chatterjee K, Chmelik M, Davies J. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">10.15479/AT:IST-2015-325-v2-1</a>","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Jessica Davies. <i>A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-325-v2-1\">https://doi.org/10.15479/AT:IST-2015-325-v2-1</a>."},"type":"technical_report"},{"department":[{"_id":"KrCh"}],"publication_identifier":{"issn":["2664-1690"]},"date_updated":"2020-07-14T23:05:07Z","title":"Reconstructing robust phylogenies of metastatic cancers","month":"12","year":"2015","date_published":"2015-12-30T00:00:00Z","author":[{"first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes","last_name":"Reiter"},{"full_name":"Makohon-Moore, Alvin","last_name":"Makohon-Moore","first_name":"Alvin"},{"first_name":"Jeffrey","last_name":"Gerold","full_name":"Gerold, Jeffrey"},{"first_name":"Ivana","last_name":"Bozic","full_name":"Bozic, Ivana"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christine","last_name":"Iacobuzio-Donahue","full_name":"Iacobuzio-Donahue, Christine"},{"full_name":"Vogelstein, Bert","last_name":"Vogelstein","first_name":"Bert"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"doi":"10.15479/AT:IST-2015-399-v1-1","pubrep_id":"399","file_date_updated":"2020-07-14T12:46:58Z","oa_version":"Published Version","page":"25","_id":"5444","publisher":"IST Austria","day":"30","date_created":"2018-12-12T11:39:22Z","publication_status":"published","alternative_title":["IST Austria Technical Report"],"abstract":[{"text":"A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.","lang":"eng"}],"status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"access_level":"open_access","file_name":"IST-2015-399-v1+1_treeomics.pdf","file_size":3533200,"content_type":"application/pdf","date_updated":"2020-07-14T12:46:58Z","relation":"main_file","checksum":"c47d33bdda06181753c0af36f16e7b5d","date_created":"2018-12-12T11:53:24Z","creator":"system","file_id":"5485"}],"type":"technical_report","citation":{"ieee":"J. Reiter <i>et al.</i>, <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria, 2015.","apa":"Reiter, J., Makohon-Moore, A., Gerold, J., Bozic, I., Chatterjee, K., Iacobuzio-Donahue, C., … Nowak, M. (2015). <i>Reconstructing robust phylogenies of metastatic cancers</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>","short":"J. Reiter, A. Makohon-Moore, J. Gerold, I. Bozic, K. Chatterjee, C. Iacobuzio-Donahue, B. Vogelstein, M. Nowak, Reconstructing Robust Phylogenies of Metastatic Cancers, IST Austria, 2015.","mla":"Reiter, Johannes, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>.","ista":"Reiter J, Makohon-Moore A, Gerold J, Bozic I, Chatterjee K, Iacobuzio-Donahue C, Vogelstein B, Nowak M. 2015. Reconstructing robust phylogenies of metastatic cancers, IST Austria, 25p.","ama":"Reiter J, Makohon-Moore A, Gerold J, et al. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">10.15479/AT:IST-2015-399-v1-1</a>","chicago":"Reiter, Johannes, Alvin Makohon-Moore, Jeffrey Gerold, Ivana Bozic, Krishnendu Chatterjee, Christine Iacobuzio-Donahue, Bert Vogelstein, and Martin Nowak. <i>Reconstructing Robust Phylogenies of Metastatic Cancers</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-399-v1-1\">https://doi.org/10.15479/AT:IST-2015-399-v1-1</a>."},"ddc":["000","576"]},{"license":"https://creativecommons.org/publicdomain/zero/1.0/","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"related_material":{"record":[{"status":"public","relation":"popular_science","id":"1603"}]},"datarep_id":"28","_id":"5549","project":[{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"date_created":"2018-12-12T12:31:29Z","file_date_updated":"2020-07-14T12:47:00Z","contributor":[{"last_name":"Kretinsky","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2015-08-13T00:00:00Z","article_processing_charge":"No","keyword":["Markov Decision Process","Decision Tree","Probabilistic Verification","Counterexample Explanation"],"ec_funded":1,"date_updated":"2024-02-21T13:52:07Z","title":"Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes","month":"08","ddc":["004"],"file":[{"file_name":"IST-2015-28-v1+2_Fellner_DataRep.zip","access_level":"open_access","relation":"main_file","checksum":"b8bcb43c0893023cda66c1b69c16ac62","content_type":"application/zip","date_updated":"2020-07-14T12:47:00Z","file_size":49557109,"creator":"system","date_created":"2018-12-12T13:02:31Z","file_id":"5597"}],"citation":{"ama":"Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. 2015. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>","chicago":"Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>.","mla":"Fellner, Andreas. <i>Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes</i>. Institute of Science and Technology Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","ista":"Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:28\">10.15479/AT:ISTA:28</a>.","apa":"Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:28\">https://doi.org/10.15479/AT:ISTA:28</a>","short":"A. Fellner, (2015).","ieee":"A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015."},"type":"research_data","abstract":[{"lang":"eng","text":"This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.\r\nThe archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.\r\nTo execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.\r\nThe archive contains scripts that (if run often enough) reproduces the data presented in the publication."}],"publist_id":"5564","has_accepted_license":"1","status":"public","publisher":"Institute of Science and Technology Austria","day":"13","doi":"10.15479/AT:ISTA:28","oa_version":"Published Version","author":[{"full_name":"Fellner, Andreas","last_name":"Fellner","id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"}],"year":"2015","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"tmp":{"legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)","image":"/images/cc_0.png"}},{"publication":"Frontiers in Environmental Science","file_date_updated":"2022-02-25T11:55:26Z","date_created":"2022-02-25T11:42:25Z","_id":"10794","project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"month":"06","title":"Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study","date_updated":"2022-02-25T11:59:23Z","ec_funded":1,"article_processing_charge":"No","keyword":["General Environmental Science"],"date_published":"2015-06-10T00:00:00Z","scopus_import":"1","volume":3,"oa":1,"intvolume":"         3","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"The authors would like to acknowledge contributions from Baptiste Mottet who performed preliminary analysis regarding parameter inference for the considered case study in a student project (Mottet, 2014/2015).\r\nThe research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement No. [291734] and from SystemsX under the project SignalX.","article_number":"42","oa_version":"Published Version","doi":"10.3389/fenvs.2015.00042","day":"10","publisher":"Frontiers","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"},"department":[{"_id":"ToHe"},{"_id":"GaTk"}],"publication_identifier":{"issn":["2296-665X"]},"year":"2015","author":[{"first_name":"Francesca","last_name":"Parise","full_name":"Parise, Francesca"},{"first_name":"John","last_name":"Lygeros","full_name":"Lygeros, John"},{"id":"4A245D00-F248-11E8-B48F-1D18A9856A87","first_name":"Jakob","orcid":"0000-0003-1615-3282","full_name":"Ruess, Jakob","last_name":"Ruess"}],"citation":{"ista":"Parise F, Lygeros J, Ruess J. 2015. Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study. Frontiers in Environmental Science. 3, 42.","mla":"Parise, Francesca, et al. “Bayesian Inference for Stochastic Individual-Based Models of Ecological Systems: A Pest Control Simulation Study.” <i>Frontiers in Environmental Science</i>, vol. 3, 42, Frontiers, 2015, doi:<a href=\"https://doi.org/10.3389/fenvs.2015.00042\">10.3389/fenvs.2015.00042</a>.","ama":"Parise F, Lygeros J, Ruess J. Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study. <i>Frontiers in Environmental Science</i>. 2015;3. doi:<a href=\"https://doi.org/10.3389/fenvs.2015.00042\">10.3389/fenvs.2015.00042</a>","chicago":"Parise, Francesca, John Lygeros, and Jakob Ruess. “Bayesian Inference for Stochastic Individual-Based Models of Ecological Systems: A Pest Control Simulation Study.” <i>Frontiers in Environmental Science</i>. Frontiers, 2015. <a href=\"https://doi.org/10.3389/fenvs.2015.00042\">https://doi.org/10.3389/fenvs.2015.00042</a>.","ieee":"F. Parise, J. Lygeros, and J. Ruess, “Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study,” <i>Frontiers in Environmental Science</i>, vol. 3. Frontiers, 2015.","short":"F. Parise, J. Lygeros, J. Ruess, Frontiers in Environmental Science 3 (2015).","apa":"Parise, F., Lygeros, J., &#38; Ruess, J. (2015). Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study. <i>Frontiers in Environmental Science</i>. Frontiers. <a href=\"https://doi.org/10.3389/fenvs.2015.00042\">https://doi.org/10.3389/fenvs.2015.00042</a>"},"type":"journal_article","file":[{"file_id":"10795","creator":"dernst","date_created":"2022-02-25T11:55:26Z","file_size":1371201,"content_type":"application/pdf","date_updated":"2022-02-25T11:55:26Z","relation":"main_file","checksum":"26c222487564e1be02a11d688d6f769d","access_level":"open_access","success":1,"file_name":"2015_FrontiersEnvironmScience_Parise.pdf"}],"article_type":"original","ddc":["000","570"],"status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"publication_status":"published","abstract":[{"text":"Mathematical models are of fundamental importance in the understanding of complex population dynamics. For instance, they can be used to predict the population evolution starting from different initial conditions or to test how a system responds to external perturbations. For this analysis to be meaningful in real applications, however, it is of paramount importance to choose an appropriate model structure and to infer the model parameters from measured data. While many parameter inference methods are available for models based on deterministic ordinary differential equations, the same does not hold for more detailed individual-based models. Here we consider, in particular, stochastic models in which the time evolution of the species abundances is described by a continuous-time Markov chain. These models are governed by a master equation that is typically difficult to solve. Consequently, traditional inference methods that rely on iterative evaluation of parameter likelihoods are computationally intractable. The aim of this paper is to present recent advances in parameter inference for continuous-time Markov chain models, based on a moment closure approximation of the parameter likelihood, and to investigate how these results can help in understanding, and ultimately controlling, complex systems in ecology. Specifically, we illustrate through an agricultural pest case study how parameters of a stochastic individual-based model can be identified from measured data and how the resulting model can be used to solve an optimal control problem in a stochastic setting. In particular, we show how the matter of determining the optimal combination of two different pest control methods can be formulated as a chance constrained optimization problem where the control action is modeled as a state reset, leading to a hybrid system formulation.","lang":"eng"}],"quality_controlled":"1"},{"department":[{"_id":"KrCh"}],"publication_identifier":{"isbn":["978-161197374-7"]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"}],"conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2015-01-06","location":"San Diego, CA, United States","start_date":"2015-01-04"},"year":"2015","oa_version":"Preprint","arxiv":1,"doi":"10.1137/1.9781611973730.69","day":"01","publisher":"SIAM","language":[{"iso":"eng"}],"status":"public","abstract":[{"lang":"eng","text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy)."}],"publication_status":"published","quality_controlled":"1","citation":{"apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2015, pp. 1018–1029). San Diego, CA, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611973730.69\">https://doi.org/10.1137/1.9781611973730.69</a>","short":"K. Chatterjee, R. Ibsen-Jensen, in:, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2015, pp. 1018–1029.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The value 1 problem under finite-memory strategies for concurrent mean-payoff games,” in <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, San Diego, CA, United States, 2015, vol. 2015, no. 1, pp. 1018–1029.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” In <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2015:1018–29. SIAM, 2015. <a href=\"https://doi.org/10.1137/1.9781611973730.69\">https://doi.org/10.1137/1.9781611973730.69</a>.","ama":"Chatterjee K, Ibsen-Jensen R. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In: <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2015. SIAM; 2015:1018-1029. doi:<a href=\"https://doi.org/10.1137/1.9781611973730.69\">10.1137/1.9781611973730.69</a>","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2015, no. 1, SIAM, 2015, pp. 1018–29, doi:<a href=\"https://doi.org/10.1137/1.9781611973730.69\">10.1137/1.9781611973730.69</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2015. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2015, 1018–1029."},"type":"conference","month":"01","title":"The value 1 problem under finite-memory strategies for concurrent mean-payoff games","date_updated":"2022-02-25T12:33:32Z","ec_funded":1,"date_published":"2015-01-01T00:00:00Z","article_processing_charge":"No","page":"1018-1029","publication":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms","date_created":"2022-02-25T12:18:43Z","external_id":{"arxiv":["1409.6690"]},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF"},{"call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"_id":"10796","volume":2015,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"1","acknowledgement":"The research was partly supported by FWF Grant No P 23499-N23, FWF NFN Grant\r\nNo S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","intvolume":"      2015","scopus_import":"1"},{"extern":"1","scopus_import":"1","intvolume":"        29","oa":1,"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","issue":"24","volume":29,"external_id":{"pmid":["26680300"]},"date_created":"2021-06-08T09:56:24Z","_id":"9532","page":"2517–2531","publication":"Genes and Development","file_date_updated":"2021-06-08T09:55:10Z","article_processing_charge":"No","date_published":"2015-12-15T00:00:00Z","month":"12","date_updated":"2021-12-14T07:58:15Z","title":"Evolution and function of genomic imprinting in plants","article_type":"review","ddc":["570"],"citation":{"ieee":"J. A. Rodrigues and D. Zilberman, “Evolution and function of genomic imprinting in plants,” <i>Genes and Development</i>, vol. 29, no. 24. Cold Spring Harbor Laboratory Press, pp. 2517–2531, 2015.","short":"J.A. Rodrigues, D. Zilberman, Genes and Development 29 (2015) 2517–2531.","apa":"Rodrigues, J. A., &#38; Zilberman, D. (2015). Evolution and function of genomic imprinting in plants. <i>Genes and Development</i>. Cold Spring Harbor Laboratory Press. <a href=\"https://doi.org/10.1101/gad.269902.115\">https://doi.org/10.1101/gad.269902.115</a>","mla":"Rodrigues, Jessica A., and Daniel Zilberman. “Evolution and Function of Genomic Imprinting in Plants.” <i>Genes and Development</i>, vol. 29, no. 24, Cold Spring Harbor Laboratory Press, 2015, pp. 2517–2531, doi:<a href=\"https://doi.org/10.1101/gad.269902.115\">10.1101/gad.269902.115</a>.","ista":"Rodrigues JA, Zilberman D. 2015. Evolution and function of genomic imprinting in plants. Genes and Development. 29(24), 2517–2531.","ama":"Rodrigues JA, Zilberman D. Evolution and function of genomic imprinting in plants. <i>Genes and Development</i>. 2015;29(24):2517–2531. doi:<a href=\"https://doi.org/10.1101/gad.269902.115\">10.1101/gad.269902.115</a>","chicago":"Rodrigues, Jessica A., and Daniel Zilberman. “Evolution and Function of Genomic Imprinting in Plants.” <i>Genes and Development</i>. Cold Spring Harbor Laboratory Press, 2015. <a href=\"https://doi.org/10.1101/gad.269902.115\">https://doi.org/10.1101/gad.269902.115</a>."},"type":"journal_article","file":[{"creator":"asandaue","date_created":"2021-06-08T09:55:10Z","file_id":"9533","file_name":"2015_GenesAndDevelopment_Rodrigues.pdf","access_level":"open_access","success":1,"checksum":"086a88cfca4677646da26ed960cb02e9","relation":"main_file","file_size":1116846,"date_updated":"2021-06-08T09:55:10Z","content_type":"application/pdf"}],"quality_controlled":"1","pmid":1,"has_accepted_license":"1","status":"public","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Genomic imprinting, an inherently epigenetic phenomenon defined by parent of origin-dependent gene expression, is observed in mammals and flowering plants. Genome-scale surveys of imprinted expression and the underlying differential epigenetic marks have led to the discovery of hundreds of imprinted plant genes and confirmed DNA and histone methylation as key regulators of plant imprinting. However, the biological roles of the vast majority of imprinted plant genes are unknown, and the evolutionary forces shaping plant imprinting remain rather opaque. Here, we review the mechanisms of plant genomic imprinting and discuss theories of imprinting evolution and biological significance in light of recent findings."}],"publication_status":"published","day":"15","publisher":"Cold Spring Harbor Laboratory Press","oa_version":"Published Version","doi":"10.1101/gad.269902.115","year":"2015","author":[{"first_name":"Jessica A.","last_name":"Rodrigues","full_name":"Rodrigues, Jessica A."},{"last_name":"Zilberman","full_name":"Zilberman, Daniel","orcid":"0000-0002-0123-8649","first_name":"Daniel","id":"6973db13-dd5f-11ea-814e-b3e5455e9ed1"}],"tmp":{"image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","short":"CC BY-NC (4.0)"},"publication_identifier":{"issn":["0890-9369"],"eissn":["1549-5477"]},"department":[{"_id":"DaZi"}]},{"date_updated":"2023-02-23T10:07:02Z","title":"Excel file containing the raw data for all figures","department":[{"_id":"ToBo"}],"month":"11","author":[{"id":"424D78A0-F248-11E8-B48F-1D18A9856A87","first_name":"Guillaume","last_name":"Chevereau","full_name":"Chevereau, Guillaume"},{"last_name":"Lukacisinova","orcid":"0000-0002-2519-8004","full_name":"Lukacisinova, Marta","first_name":"Marta","id":"4342E402-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tugce","last_name":"Batur","full_name":"Batur, Tugce"},{"first_name":"Aysegul","full_name":"Guvenek, Aysegul","last_name":"Guvenek"},{"first_name":"Dilay Hazal","full_name":"Ayhan, Dilay Hazal","last_name":"Ayhan"},{"full_name":"Toprak, Erdal","last_name":"Toprak","first_name":"Erdal"},{"last_name":"Bollenbach","orcid":"0000-0003-4398-476X","full_name":"Bollenbach, Mark Tobias","first_name":"Mark Tobias","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2015-11-18T00:00:00Z","year":"2015","article_processing_charge":"No","doi":"10.1371/journal.pbio.1002299.s001","oa_version":"Published Version","_id":"9711","publisher":"Public Library of Science","date_created":"2021-07-23T11:53:50Z","day":"18","related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"1619"}]},"status":"public","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","type":"research_data_reference","citation":{"ista":"Chevereau G, Lukacisinova M, Batur T, Guvenek A, Ayhan DH, Toprak E, Bollenbach MT. 2015. Excel file containing the raw data for all figures, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pbio.1002299.s001\">10.1371/journal.pbio.1002299.s001</a>.","mla":"Chevereau, Guillaume, et al. <i>Excel File Containing the Raw Data for All Figures</i>. Public Library of Science, 2015, doi:<a href=\"https://doi.org/10.1371/journal.pbio.1002299.s001\">10.1371/journal.pbio.1002299.s001</a>.","ama":"Chevereau G, Lukacisinova M, Batur T, et al. Excel file containing the raw data for all figures. 2015. doi:<a href=\"https://doi.org/10.1371/journal.pbio.1002299.s001\">10.1371/journal.pbio.1002299.s001</a>","chicago":"Chevereau, Guillaume, Marta Lukacisinova, Tugce Batur, Aysegul Guvenek, Dilay Hazal Ayhan, Erdal Toprak, and Mark Tobias Bollenbach. “Excel File Containing the Raw Data for All Figures.” Public Library of Science, 2015. <a href=\"https://doi.org/10.1371/journal.pbio.1002299.s001\">https://doi.org/10.1371/journal.pbio.1002299.s001</a>.","ieee":"G. Chevereau <i>et al.</i>, “Excel file containing the raw data for all figures.” Public Library of Science, 2015.","short":"G. Chevereau, M. Lukacisinova, T. Batur, A. Guvenek, D.H. Ayhan, E. Toprak, M.T. Bollenbach, (2015).","apa":"Chevereau, G., Lukacisinova, M., Batur, T., Guvenek, A., Ayhan, D. H., Toprak, E., &#38; Bollenbach, M. T. (2015). Excel file containing the raw data for all figures. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pbio.1002299.s001\">https://doi.org/10.1371/journal.pbio.1002299.s001</a>"}},{"oa_version":"Published Version","doi":"10.1371/journal.pgen.1005639.s001","day":"06","date_created":"2021-07-23T12:00:37Z","_id":"9712","publisher":"Public Library of Science","month":"11","department":[{"_id":"NiBa"},{"_id":"CaGu"},{"_id":"GaTk"}],"title":"Other fitness models for comparison & for interacting TFBSs","date_updated":"2025-05-28T11:57:04Z","year":"2015","article_processing_charge":"No","date_published":"2015-11-06T00:00:00Z","author":[{"id":"37C323C6-F248-11E8-B48F-1D18A9856A87","first_name":"Murat","full_name":"Tugrul, Murat","orcid":"0000-0002-8523-0758","last_name":"Tugrul"},{"id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","first_name":"Tiago","orcid":"0000-0003-2361-3953","full_name":"Paixao, Tiago","last_name":"Paixao"},{"full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H"},{"id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","first_name":"Gašper","orcid":"0000-0002-6699-1455","full_name":"Tkačik, Gašper","last_name":"Tkačik"}],"type":"research_data_reference","citation":{"ama":"Tugrul M, Paixao T, Barton NH, Tkačik G. Other fitness models for comparison &#38; for interacting TFBSs. 2015. doi:<a href=\"https://doi.org/10.1371/journal.pgen.1005639.s001\">10.1371/journal.pgen.1005639.s001</a>","chicago":"Tugrul, Murat, Tiago Paixao, Nicholas H Barton, and Gašper Tkačik. “Other Fitness Models for Comparison &#38; for Interacting TFBSs.” Public Library of Science, 2015. <a href=\"https://doi.org/10.1371/journal.pgen.1005639.s001\">https://doi.org/10.1371/journal.pgen.1005639.s001</a>.","mla":"Tugrul, Murat, et al. <i>Other Fitness Models for Comparison &#38; for Interacting TFBSs</i>. Public Library of Science, 2015, doi:<a href=\"https://doi.org/10.1371/journal.pgen.1005639.s001\">10.1371/journal.pgen.1005639.s001</a>.","ista":"Tugrul M, Paixao T, Barton NH, Tkačik G. 2015. Other fitness models for comparison &#38; for interacting TFBSs, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pgen.1005639.s001\">10.1371/journal.pgen.1005639.s001</a>.","apa":"Tugrul, M., Paixao, T., Barton, N. H., &#38; Tkačik, G. (2015). Other fitness models for comparison &#38; for interacting TFBSs. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pgen.1005639.s001\">https://doi.org/10.1371/journal.pgen.1005639.s001</a>","short":"M. Tugrul, T. Paixao, N.H. Barton, G. Tkačik, (2015).","ieee":"M. Tugrul, T. Paixao, N. H. Barton, and G. Tkačik, “Other fitness models for comparison &#38; for interacting TFBSs.” Public Library of Science, 2015."},"status":"public","related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"1666"}]},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf"},{"doi":"10.1371/journal.pcbi.1004541.s001","oa_version":"Published Version","_id":"9714","publisher":"Public Library of Science ","date_created":"2021-07-23T12:05:28Z","day":"23","date_updated":"2023-02-23T10:04:35Z","title":"An exploration of the universe of polyglutamine structures - submission to PLOS journals","department":[{"_id":"CaHe"}],"month":"10","author":[{"first_name":"Àngel","full_name":"Gómez Sicilia, Àngel","last_name":"Gómez Sicilia"},{"last_name":"Sikora","full_name":"Sikora, Mateusz K","id":"2F74BCDE-F248-11E8-B48F-1D18A9856A87","first_name":"Mateusz K"},{"last_name":"Cieplak","full_name":"Cieplak, Marek","first_name":"Marek"},{"first_name":"Mariano","last_name":"Carrión Vázquez","full_name":"Carrión Vázquez, Mariano"}],"date_published":"2015-10-23T00:00:00Z","year":"2015","article_processing_charge":"No","citation":{"ieee":"À. Gómez Sicilia, M. K. Sikora, M. Cieplak, and M. Carrión Vázquez, “An exploration of the universe of polyglutamine structures - submission to PLOS journals.” Public Library of Science , 2015.","apa":"Gómez Sicilia, À., Sikora, M. K., Cieplak, M., &#38; Carrión Vázquez, M. (2015). An exploration of the universe of polyglutamine structures - submission to PLOS journals. Public Library of Science . <a href=\"https://doi.org/10.1371/journal.pcbi.1004541.s001\">https://doi.org/10.1371/journal.pcbi.1004541.s001</a>","short":"À. Gómez Sicilia, M.K. Sikora, M. Cieplak, M. Carrión Vázquez, (2015).","mla":"Gómez Sicilia, Àngel, et al. <i>An Exploration of the Universe of Polyglutamine Structures - Submission to PLOS Journals</i>. Public Library of Science , 2015, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1004541.s001\">10.1371/journal.pcbi.1004541.s001</a>.","ista":"Gómez Sicilia À, Sikora MK, Cieplak M, Carrión Vázquez M. 2015. An exploration of the universe of polyglutamine structures - submission to PLOS journals, Public Library of Science , <a href=\"https://doi.org/10.1371/journal.pcbi.1004541.s001\">10.1371/journal.pcbi.1004541.s001</a>.","ama":"Gómez Sicilia À, Sikora MK, Cieplak M, Carrión Vázquez M. An exploration of the universe of polyglutamine structures - submission to PLOS journals. 2015. doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1004541.s001\">10.1371/journal.pcbi.1004541.s001</a>","chicago":"Gómez Sicilia, Àngel, Mateusz K Sikora, Marek Cieplak, and Mariano Carrión Vázquez. “An Exploration of the Universe of Polyglutamine Structures - Submission to PLOS Journals.” Public Library of Science , 2015. <a href=\"https://doi.org/10.1371/journal.pcbi.1004541.s001\">https://doi.org/10.1371/journal.pcbi.1004541.s001</a>."},"type":"research_data_reference","related_material":{"record":[{"status":"public","relation":"used_in_publication","id":"1566"}]},"status":"public","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf"},{"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","status":"public","related_material":{"record":[{"id":"1809","relation":"used_in_publication","status":"public"}]},"citation":{"ama":"Trubenova B, Novak S, Hager R. Mathematical inference of the results. 2015. doi:<a href=\"https://doi.org/10.1371/journal.pone.0126907.s001\">10.1371/journal.pone.0126907.s001</a>","chicago":"Trubenova, Barbora, Sebastian Novak, and Reinmar Hager. “Mathematical Inference of the Results.” Public Library of Science, 2015. <a href=\"https://doi.org/10.1371/journal.pone.0126907.s001\">https://doi.org/10.1371/journal.pone.0126907.s001</a>.","mla":"Trubenova, Barbora, et al. <i>Mathematical Inference of the Results</i>. Public Library of Science, 2015, doi:<a href=\"https://doi.org/10.1371/journal.pone.0126907.s001\">10.1371/journal.pone.0126907.s001</a>.","ista":"Trubenova B, Novak S, Hager R. 2015. Mathematical inference of the results, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pone.0126907.s001\">10.1371/journal.pone.0126907.s001</a>.","apa":"Trubenova, B., Novak, S., &#38; Hager, R. (2015). Mathematical inference of the results. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0126907.s001\">https://doi.org/10.1371/journal.pone.0126907.s001</a>","short":"B. Trubenova, S. Novak, R. Hager, (2015).","ieee":"B. Trubenova, S. Novak, and R. Hager, “Mathematical inference of the results.” Public Library of Science, 2015."},"type":"research_data_reference","year":"2015","article_processing_charge":"No","author":[{"first_name":"Barbora","id":"42302D54-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6873-2967","full_name":"Trubenova, Barbora","last_name":"Trubenova"},{"full_name":"Novak, Sebastian","last_name":"Novak","first_name":"Sebastian","id":"461468AE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Reinmar","last_name":"Hager","full_name":"Hager, Reinmar"}],"date_published":"2015-05-18T00:00:00Z","month":"05","department":[{"_id":"NiBa"}],"title":"Mathematical inference of the results","date_updated":"2023-02-23T10:15:25Z","day":"18","date_created":"2021-07-23T12:11:30Z","_id":"9715","publisher":"Public Library of Science","oa_version":"Published Version","doi":"10.1371/journal.pone.0126907.s001"},{"year":"2015","article_processing_charge":"No","date_published":"2015-03-23T00:00:00Z","author":[{"id":"36A5845C-F248-11E8-B48F-1D18A9856A87","first_name":"Tamar","last_name":"Friedlander","full_name":"Friedlander, Tamar"},{"full_name":"Mayo, Avraham E.","last_name":"Mayo","first_name":"Avraham E."},{"last_name":"Tlusty","full_name":"Tlusty, Tsvi","first_name":"Tsvi"},{"last_name":"Alon","full_name":"Alon, Uri","first_name":"Uri"}],"department":[{"_id":"GaTk"}],"title":"Supporting information text","date_updated":"2023-02-23T10:16:13Z","month":"03","publisher":"Public Library of Science","_id":"9718","day":"23","date_created":"2021-07-26T08:35:23Z","doi":"10.1371/journal.pcbi.1004055.s001","oa_version":"Published Version","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","related_material":{"record":[{"id":"1827","relation":"used_in_publication","status":"public"}]},"status":"public","citation":{"mla":"Friedlander, Tamar, et al. <i>Supporting Information Text</i>. Public Library of Science, 2015, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1004055.s001\">10.1371/journal.pcbi.1004055.s001</a>.","ista":"Friedlander T, Mayo AE, Tlusty T, Alon U. 2015. Supporting information text, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pcbi.1004055.s001\">10.1371/journal.pcbi.1004055.s001</a>.","chicago":"Friedlander, Tamar, Avraham E. Mayo, Tsvi Tlusty, and Uri Alon. “Supporting Information Text.” Public Library of Science, 2015. <a href=\"https://doi.org/10.1371/journal.pcbi.1004055.s001\">https://doi.org/10.1371/journal.pcbi.1004055.s001</a>.","ama":"Friedlander T, Mayo AE, Tlusty T, Alon U. Supporting information text. 2015. doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1004055.s001\">10.1371/journal.pcbi.1004055.s001</a>","ieee":"T. Friedlander, A. E. Mayo, T. Tlusty, and U. Alon, “Supporting information text.” Public Library of Science, 2015.","apa":"Friedlander, T., Mayo, A. E., Tlusty, T., &#38; Alon, U. (2015). Supporting information text. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1004055.s001\">https://doi.org/10.1371/journal.pcbi.1004055.s001</a>","short":"T. Friedlander, A.E. Mayo, T. Tlusty, U. Alon, (2015)."},"type":"research_data_reference"},{"department":[{"_id":"CaGu"}],"date_updated":"2023-09-05T13:46:04Z","title":"Data from: Adaptation to parasites and costs of parasite resistance in mutator and non-mutator bacteria","month":"12","article_processing_charge":"No","year":"2015","date_published":"2015-12-21T00:00:00Z","author":[{"last_name":"Wielgoss","full_name":"Wielgoss, Sébastien","first_name":"Sébastien"},{"first_name":"Tobias","id":"2C471CFA-F248-11E8-B48F-1D18A9856A87","last_name":"Bergmiller","orcid":"0000-0001-5396-4346","full_name":"Bergmiller, Tobias"},{"last_name":"Bischofberger","full_name":"Bischofberger, Anna M.","first_name":"Anna M."},{"last_name":"Hall","full_name":"Hall, Alex R.","first_name":"Alex R."}],"doi":"10.5061/dryad.cj910","oa_version":"Published Version","publisher":"Dryad","_id":"9719","day":"21","date_created":"2021-07-26T08:44:04Z","related_material":{"record":[{"status":"public","relation":"used_in_publication","id":"5749"}]},"main_file_link":[{"url":"https://doi.org/10.5061/dryad.cj910","open_access":"1"}],"abstract":[{"text":"Parasitism creates selection for resistance mechanisms in host populations and is hypothesized to promote increased host evolvability. However, the influence of these traits on host evolution when parasites are no longer present is unclear. We used experimental evolution and whole-genome sequencing of Escherichia coli to determine the effects of past and present exposure to parasitic viruses (phages) on the spread of mutator alleles, resistance, and bacterial competitive fitness. We found that mutator alleles spread rapidly during adaptation to any of four different phage species, and this pattern was even more pronounced with multiple phages present simultaneously. However, hypermutability did not detectably accelerate adaptation in the absence of phages and recovery of fitness costs associated with resistance. Several lineages evolved phage resistance through elevated mucoidy, and during subsequent evolution in phage-free conditions they rapidly reverted to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this phenotypic reversion was achieved by additional genetic changes rather than by genotypic reversion of the initial resistance mutations. Insertion sequence (IS) elements played a key role in both the acquisition of resistance and adaptation in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions were not more frequent in mutator lineages. Our results provide a genetic explanation for rapid reversion of mucoidy, a phenotype observed in other bacterial species including human pathogens. Moreover, this demonstrates that the types of genetic change underlying adaptation to fitness costs, and consequently the impact of evolvability mechanisms such as increased point-mutation rates, depend critically on the mechanism of resistance.","lang":"eng"}],"status":"public","oa":1,"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","citation":{"ieee":"S. Wielgoss, T. Bergmiller, A. M. Bischofberger, and A. R. Hall, “Data from: Adaptation to parasites and costs of parasite resistance in mutator and non-mutator bacteria.” Dryad, 2015.","short":"S. Wielgoss, T. Bergmiller, A.M. Bischofberger, A.R. Hall, (2015).","apa":"Wielgoss, S., Bergmiller, T., Bischofberger, A. M., &#38; Hall, A. R. (2015). Data from: Adaptation to parasites and costs of parasite resistance in mutator and non-mutator bacteria. Dryad. <a href=\"https://doi.org/10.5061/dryad.cj910\">https://doi.org/10.5061/dryad.cj910</a>","mla":"Wielgoss, Sébastien, et al. <i>Data from: Adaptation to Parasites and Costs of Parasite Resistance in Mutator and Non-Mutator Bacteria</i>. Dryad, 2015, doi:<a href=\"https://doi.org/10.5061/dryad.cj910\">10.5061/dryad.cj910</a>.","ista":"Wielgoss S, Bergmiller T, Bischofberger AM, Hall AR. 2015. Data from: Adaptation to parasites and costs of parasite resistance in mutator and non-mutator bacteria, Dryad, <a href=\"https://doi.org/10.5061/dryad.cj910\">10.5061/dryad.cj910</a>.","ama":"Wielgoss S, Bergmiller T, Bischofberger AM, Hall AR. Data from: Adaptation to parasites and costs of parasite resistance in mutator and non-mutator bacteria. 2015. doi:<a href=\"https://doi.org/10.5061/dryad.cj910\">10.5061/dryad.cj910</a>","chicago":"Wielgoss, Sébastien, Tobias Bergmiller, Anna M. Bischofberger, and Alex R. Hall. “Data from: Adaptation to Parasites and Costs of Parasite Resistance in Mutator and Non-Mutator Bacteria.” Dryad, 2015. <a href=\"https://doi.org/10.5061/dryad.cj910\">https://doi.org/10.5061/dryad.cj910</a>."},"type":"research_data_reference"},{"oa":1,"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.5061/dryad.dj2bf"}],"related_material":{"record":[{"id":"1830","relation":"used_in_publication","status":"public"}]},"abstract":[{"lang":"eng","text":"To prevent epidemics, insect societies have evolved collective disease defences that are highly effective at curing exposed individuals and limiting disease transmission to healthy group members. Grooming is an important sanitary behaviour—either performed towards oneself (self-grooming) or towards others (allogrooming)—to remove infectious agents from the body surface of exposed individuals, but at the risk of disease contraction by the groomer. We use garden ants (Lasius neglectus) and the fungal pathogen Metarhizium as a model system to study how pathogen presence affects self-grooming and allogrooming between exposed and healthy individuals. We develop an epidemiological SIS model to explore how experimentally observed grooming patterns affect disease spread within the colony, thereby providing a direct link between the expression and direction of sanitary behaviours, and their effects on colony-level epidemiology. We find that fungus-exposed ants increase self-grooming, while simultaneously decreasing allogrooming. This behavioural modulation seems universally adaptive and is predicted to contain disease spread in a great variety of host–pathogen systems. In contrast, allogrooming directed towards pathogen-exposed individuals might both increase and decrease disease risk. Our model reveals that the effect of allogrooming depends on the balance between pathogen infectiousness and efficiency of social host defences, which are likely to vary across host–pathogen systems."}],"type":"research_data_reference","citation":{"ieee":"F. Theis, L. V. Ugelvig, C. Marr, and S. Cremer, “Data from: Opposing effects of allogrooming on disease transmission in ant societies.” Dryad, 2015.","apa":"Theis, F., Ugelvig, L. V., Marr, C., &#38; Cremer, S. (2015). Data from: Opposing effects of allogrooming on disease transmission in ant societies. Dryad. <a href=\"https://doi.org/10.5061/dryad.dj2bf\">https://doi.org/10.5061/dryad.dj2bf</a>","short":"F. Theis, L.V. Ugelvig, C. Marr, S. Cremer, (2015).","ista":"Theis F, Ugelvig LV, Marr C, Cremer S. 2015. Data from: Opposing effects of allogrooming on disease transmission in ant societies, Dryad, <a href=\"https://doi.org/10.5061/dryad.dj2bf\">10.5061/dryad.dj2bf</a>.","mla":"Theis, Fabian, et al. <i>Data from: Opposing Effects of Allogrooming on Disease Transmission in Ant Societies</i>. Dryad, 2015, doi:<a href=\"https://doi.org/10.5061/dryad.dj2bf\">10.5061/dryad.dj2bf</a>.","chicago":"Theis, Fabian, Line V Ugelvig, Carsten Marr, and Sylvia Cremer. “Data from: Opposing Effects of Allogrooming on Disease Transmission in Ant Societies.” Dryad, 2015. <a href=\"https://doi.org/10.5061/dryad.dj2bf\">https://doi.org/10.5061/dryad.dj2bf</a>.","ama":"Theis F, Ugelvig LV, Marr C, Cremer S. Data from: Opposing effects of allogrooming on disease transmission in ant societies. 2015. doi:<a href=\"https://doi.org/10.5061/dryad.dj2bf\">10.5061/dryad.dj2bf</a>"},"article_processing_charge":"No","year":"2015","author":[{"last_name":"Theis","full_name":"Theis, Fabian","first_name":"Fabian"},{"full_name":"Ugelvig, Line V","orcid":"0000-0003-1832-8883","last_name":"Ugelvig","first_name":"Line V","id":"3DC97C8E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Carsten","full_name":"Marr, Carsten","last_name":"Marr"},{"full_name":"Cremer, Sylvia","orcid":"0000-0002-2193-3868","last_name":"Cremer","id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","first_name":"Sylvia"}],"date_published":"2015-12-29T00:00:00Z","month":"12","department":[{"_id":"SyCr"}],"title":"Data from: Opposing effects of allogrooming on disease transmission in ant societies","date_updated":"2023-02-23T10:16:22Z","day":"29","date_created":"2021-07-26T09:38:36Z","_id":"9721","publisher":"Dryad","oa_version":"Published Version","doi":"10.5061/dryad.dj2bf"},{"related_material":{"record":[{"id":"1793","status":"public","relation":"used_in_publication"}]},"status":"public","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","citation":{"short":"O. Symonova, C. Topp, H. Edelsbrunner, (2015).","apa":"Symonova, O., Topp, C., &#38; Edelsbrunner, H. (2015). Root traits computed by DynamicRoots for the maize root shown in fig 2. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0127657.s001\">https://doi.org/10.1371/journal.pone.0127657.s001</a>","ieee":"O. Symonova, C. Topp, and H. Edelsbrunner, “Root traits computed by DynamicRoots for the maize root shown in fig 2.” Public Library of Science, 2015.","ama":"Symonova O, Topp C, Edelsbrunner H. Root traits computed by DynamicRoots for the maize root shown in fig 2. 2015. doi:<a href=\"https://doi.org/10.1371/journal.pone.0127657.s001\">10.1371/journal.pone.0127657.s001</a>","chicago":"Symonova, Olga, Christopher Topp, and Herbert Edelsbrunner. “Root Traits Computed by DynamicRoots for the Maize Root Shown in Fig 2.” Public Library of Science, 2015. <a href=\"https://doi.org/10.1371/journal.pone.0127657.s001\">https://doi.org/10.1371/journal.pone.0127657.s001</a>.","mla":"Symonova, Olga, et al. <i>Root Traits Computed by DynamicRoots for the Maize Root Shown in Fig 2</i>. Public Library of Science, 2015, doi:<a href=\"https://doi.org/10.1371/journal.pone.0127657.s001\">10.1371/journal.pone.0127657.s001</a>.","ista":"Symonova O, Topp C, Edelsbrunner H. 2015. Root traits computed by DynamicRoots for the maize root shown in fig 2, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pone.0127657.s001\">10.1371/journal.pone.0127657.s001</a>."},"type":"research_data_reference","department":[{"_id":"MaJö"},{"_id":"HeEd"}],"title":"Root traits computed by DynamicRoots for the maize root shown in fig 2","date_updated":"2023-02-23T10:14:42Z","month":"06","article_processing_charge":"No","year":"2015","author":[{"id":"3C0C7BC6-F248-11E8-B48F-1D18A9856A87","first_name":"Olga","last_name":"Symonova","full_name":"Symonova, Olga"},{"last_name":"Topp","full_name":"Topp, Christopher","first_name":"Christopher"},{"last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2015-06-01T00:00:00Z","doi":"10.1371/journal.pone.0127657.s001","oa_version":"Published Version","publisher":"Public Library of Science","_id":"9737","day":"01","date_created":"2021-07-28T06:20:13Z"}]