[{"_id":"5436","type":"technical_report","pubrep_id":"331","status":"public","citation":{"mla":"Chatterjee, Krishnendu, et al. Nested Weighted Automata. IST Austria, 2015, doi:10.15479/AT:IST-2015-170-v2-2.","ama":"Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-170-v2-2","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). Nested weighted automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-170-v2-2","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, Nested weighted automata. IST Austria, 2015.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. Nested Weighted Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-170-v2-2.","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p."},"date_updated":"2023-02-23T12:25:21Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger"},{"full_name":"Otop, Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Nested weighted automata","file_date_updated":"2020-07-14T12:46:54Z","abstract":[{"lang":"eng","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."}],"oa_version":"Published Version","oa":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","month":"04","publication_status":"published","year":"2015","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"file":[{"file_size":569991,"date_updated":"2020-07-14T12:46:54Z","creator":"system","file_name":"IST-2015-170-v2+2_report.pdf","date_created":"2018-12-12T11:54:19Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"3c402f47d3669c28d04d1af405a08e3f","file_id":"5541"}],"day":"24","page":"29","date_created":"2018-12-12T11:39:19Z","date_published":"2015-04-24T00:00:00Z","related_material":{"record":[{"id":"1656","status":"public","relation":"later_version"},{"relation":"later_version","id":"467","status":"public"},{"relation":"earlier_version","id":"5415","status":"public"}]},"doi":"10.15479/AT:IST-2015-170-v2-2"},{"date_created":"2018-12-11T11:53:19Z","doi":"10.1109/LICS.2015.74","date_published":"2015-07-01T00:00:00Z","page":"750 - 761","publication":"LICS","day":"01","year":"2015","has_accepted_license":"1","oa":1,"publisher":"IEEE","quality_controlled":"1","acknowledgement":"A technical report of the article is available at: https://research-explorer.app.ist.ac.at/record/5439","title":"The target discounted-sum problem","article_processing_charge":"No","publist_id":"5491","author":[{"id":"31E297B6-F248-11E8-B48F-1D18A9856A87","first_name":"Udi","full_name":"Boker, Udi","last_name":"Boker"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger"},{"first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem. LICS. LICS: Logic in Computer ScienceLogic in Computer Science, 750–761.","chicago":"Boker, Udi, Thomas A Henzinger, and Jan Otop. “The Target Discounted-Sum Problem.” In LICS, 750–61. Logic in Computer Science. IEEE, 2015. https://doi.org/10.1109/LICS.2015.74.","ieee":"U. Boker, T. A. Henzinger, and J. Otop, “The target discounted-sum problem,” in LICS, Kyoto, Japan, 2015, pp. 750–761.","short":"U. Boker, T.A. Henzinger, J. Otop, in:, LICS, IEEE, 2015, pp. 750–761.","ama":"Boker U, Henzinger TA, Otop J. The target discounted-sum problem. In: LICS. Logic in Computer Science. IEEE; 2015:750-761. doi:10.1109/LICS.2015.74","apa":"Boker, U., Henzinger, T. A., & Otop, J. (2015). The target discounted-sum problem. In LICS (pp. 750–761). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.74","mla":"Boker, Udi, et al. “The Target Discounted-Sum Problem.” LICS, IEEE, 2015, pp. 750–61, doi:10.1109/LICS.2015.74."},"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5439"}]},"language":[{"iso":"eng"}],"file":[{"date_created":"2020-05-15T08:53:29Z","file_name":"2015_LICS_Boker.pdf","date_updated":"2020-07-14T12:45:10Z","file_size":340215,"creator":"dernst","file_id":"7852","checksum":"6abebca9c1a620e9e103a8f9222befac","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"publication_status":"published","publication_identifier":{"eisbn":["978-1-4799-8875-4 "],"issn":["1043-6871 "]},"month":"07","scopus_import":1,"oa_version":"Submitted Version","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"}],"file_date_updated":"2020-07-14T12:45:10Z","department":[{"_id":"ToHe"}],"ddc":["000"],"date_updated":"2023-02-23T12:26:27Z","status":"public","conference":{"end_date":"2015-07-10","location":"Kyoto, Japan","start_date":"2015-007-06","name":"LICS: Logic in Computer Science"},"type":"conference","_id":"1659","series_title":"Logic in Computer Science"},{"project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International Colloquium, Springer Nature, 2015, pp. 121–133.","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, “Edit distance for pushdown automata,” in 42nd International Colloquium, Kyoto, Japan, 2015, vol. 9135, no. Part II, pp. 121–133.","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown automata. In: 42nd International Colloquium. Vol 9135. Springer Nature; 2015:121-133. doi:10.1007/978-3-662-47666-6_10","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit distance for pushdown automata. In 42nd International Colloquium (Vol. 9135, pp. 121–133). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47666-6_10","mla":"Chatterjee, Krishnendu, et al. “Edit Distance for Pushdown Automata.” 42nd International Colloquium, vol. 9135, no. Part II, Springer Nature, 2015, pp. 121–33, doi:10.1007/978-3-662-47666-6_10.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata. 42nd International Colloquium. ICALP: Automata, Languages and Programming, LNCS, vol. 9135, 121–133.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. “Edit Distance for Pushdown Automata.” In 42nd International Colloquium, 9135:121–33. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47666-6_10."},"title":"Edit distance for pushdown automata","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop"}],"publist_id":"5556","external_id":{"arxiv":["1504.08259"]},"article_processing_charge":"No","publisher":"Springer Nature","quality_controlled":"1","oa":1,"day":"01","publication":"42nd International Colloquium","year":"2015","date_published":"2015-07-01T00:00:00Z","doi":"10.1007/978-3-662-47666-6_10","date_created":"2018-12-11T11:53:01Z","page":"121 - 133","_id":"1610","status":"public","pubrep_id":"321","type":"conference","conference":{"start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan","name":"ICALP: Automata, Languages and Programming"},"date_updated":"2023-02-23T12:26:24Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"oa_version":"None","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. The problem of computing edit distance to pushdown automata is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k."}],"month":"07","intvolume":" 9135","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1504.08259"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-662-47665-9"]},"publication_status":"published","volume":9135,"related_material":{"record":[{"relation":"later_version","id":"465","status":"public"},{"relation":"earlier_version","status":"public","id":"5438"}]},"issue":"Part II","ec_funded":1},{"_id":"5437","status":"public","pubrep_id":"333","type":"technical_report","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"citation":{"mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-330-v2-1.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-330-v2-1","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-330-v2-1","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-330-v2-1.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p."},"date_updated":"2023-02-23T12:26:05Z","file_date_updated":"2020-07-14T12:46:54Z","title":"Faster algorithms for quantitative verification in constant treewidth graphs","department":[{"_id":"KrCh"}],"author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"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":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"}],"oa_version":"Published Version","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. "}],"month":"04","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"day":"27","file":[{"file_size":1072137,"date_updated":"2020-07-14T12:46:54Z","creator":"system","file_name":"IST-2015-330-v2+1_main.pdf","date_created":"2018-12-12T11:53:12Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"f5917c20f84018b362d385c000a2e123","file_id":"5473"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"publication_status":"published","year":"2015","date_published":"2015-04-27T00:00:00Z","doi":"10.15479/AT:IST-2015-330-v2-1","related_material":{"record":[{"id":"1607","status":"public","relation":"later_version"},{"status":"public","id":"5430","relation":"earlier_version"}]},"date_created":"2018-12-12T11:39:19Z","page":"27"},{"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-319-v1-1.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-319-v1-1","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-319-v1-1","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-319-v1-1."},"date_updated":"2023-02-23T12:26:22Z","file_date_updated":"2020-07-14T12:46:52Z","title":"Faster algorithms for quantitative verification in constant treewidth graphs","department":[{"_id":"KrCh"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"}],"_id":"5430","status":"public","pubrep_id":"319","type":"technical_report","day":"10","file":[{"file_id":"5482","checksum":"62c6ea01e342553dcafb88a070fb1ad5","content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:21Z","file_name":"IST-2015-319-v1+1_long.pdf","date_updated":"2020-07-14T12:46:52Z","file_size":1089651,"creator":"system"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"publication_status":"published","year":"2015","doi":"10.15479/AT:IST-2015-319-v1-1","date_published":"2015-02-10T00:00:00Z","related_material":{"record":[{"id":"1607","status":"public","relation":"later_version"},{"status":"public","id":"5437","relation":"later_version"}]},"date_created":"2018-12-12T11:39:17Z","page":"31","oa_version":"Published Version","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. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks."}],"month":"02","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1},{"citation":{"chicago":"Boker, Udi, Thomas A Henzinger, and Jan Otop. The Target Discounted-Sum Problem. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-335-v1-1.","ista":"Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST Austria, 20p.","mla":"Boker, Udi, et al. The Target Discounted-Sum Problem. IST Austria, 2015, doi:10.15479/AT:IST-2015-335-v1-1.","ieee":"U. Boker, T. A. Henzinger, and J. Otop, The target discounted-sum problem. 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., & Otop, J. (2015). The target discounted-sum problem. IST Austria. https://doi.org/10.15479/AT:IST-2015-335-v1-1","ama":"Boker U, Henzinger TA, Otop J. The Target Discounted-Sum Problem. IST Austria; 2015. doi:10.15479/AT:IST-2015-335-v1-1"},"date_updated":"2023-02-23T10:08:48Z","ddc":["004","512","513"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"31E297B6-F248-11E8-B48F-1D18A9856A87","first_name":"Udi","last_name":"Boker","full_name":"Boker, Udi"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2020-07-14T12:46:55Z","title":"The target discounted-sum problem","department":[{"_id":"ToHe"}],"_id":"5439","type":"technical_report","status":"public","pubrep_id":"335","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","publication_status":"published","year":"2015","day":"18","file":[{"date_created":"2018-12-12T11:53:55Z","file_name":"IST-2015-335-v1+1_report.pdf","creator":"system","date_updated":"2020-07-14T12:46:55Z","file_size":589619,"checksum":"40405907aa012acece1bc26cf0be554d","file_id":"5517","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"page":"20","doi":"10.15479/AT:IST-2015-335-v1-1","date_published":"2015-05-18T00:00:00Z","related_material":{"record":[{"id":"1659","status":"public","relation":"later_version"}]},"date_created":"2018-12-12T11:39:20Z","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"}],"oa_version":"Published Version","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa":1,"month":"05"},{"_id":"5438","status":"public","pubrep_id":"334","type":"technical_report","ddc":["004"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T12:20:08Z","citation":{"ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. Edit Distance for Pushdown Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-334-v1-1.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015.","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, Edit distance for pushdown automata. IST Austria, 2015.","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit Distance for Pushdown Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-334-v1-1","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit distance for pushdown automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-334-v1-1","mla":"Chatterjee, Krishnendu, et al. Edit Distance for Pushdown Automata. IST Austria, 2015, doi:10.15479/AT:IST-2015-334-v1-1."},"title":"Edit distance for pushdown automata","file_date_updated":"2020-07-14T12:46:55Z","department":[{"_id":"KrCh"}],"author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan"}],"oa_version":"Published Version","abstract":[{"text":"The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.\r\nThe problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. ","lang":"eng"}],"month":"05","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"day":"05","file":[{"file_size":422573,"date_updated":"2020-07-14T12:46:55Z","creator":"system","file_name":"IST-2015-334-v1+1_report.pdf","date_created":"2018-12-12T11:53:56Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"5518","checksum":"8a5f2d77560e552af87eb1982437a43b"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","publication_status":"published","year":"2015","related_material":{"record":[{"relation":"later_version","id":"1610","status":"public"},{"id":"465","status":"public","relation":"later_version"}]},"doi":"10.15479/AT:IST-2015-334-v1-1","date_published":"2015-05-05T00:00:00Z","date_created":"2018-12-12T11:39:20Z","page":"15"},{"type":"technical_report","status":"public","pubrep_id":"338","_id":"5440","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"department":[{"_id":"KrCh"}],"title":"The complexity of evolutionary games on graphs","file_date_updated":"2020-07-14T12:46:56Z","citation":{"chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v2-2.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p.","mla":"Chatterjee, Krishnendu, et al. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v2-2.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, The complexity of evolutionary games on graphs. IST Austria, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015). The complexity of evolutionary games on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v2-2","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. The Complexity of Evolutionary Games on Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v2-2"},"date_updated":"2023-02-23T12:26:10Z","ddc":["005","576"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa":1,"month":"06","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"}],"oa_version":"Published Version","page":"18","date_published":"2015-06-16T00:00:00Z","related_material":{"record":[{"id":"5421","status":"public","relation":"earlier_version"},{"relation":"earlier_version","status":"public","id":"5432"}]},"doi":"10.15479/AT:IST-2015-323-v2-2","date_created":"2018-12-12T11:39:21Z","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"year":"2015","publication_status":"published","day":"16","file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5484","checksum":"66aace7d367032af97c15e35c9be9636","date_updated":"2020-07-14T12:46:56Z","file_size":466161,"creator":"system","date_created":"2018-12-12T11:53:23Z","file_name":"IST-2015-323-v2+2_main.pdf"}],"language":[{"iso":"eng"}]},{"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","publication_status":"published","year":"2015","day":"19","file":[{"creator":"system","date_updated":"2020-07-14T12:46:53Z","file_size":576347,"date_created":"2018-12-12T11:53:57Z","file_name":"IST-2015-323-v1+1_main.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5519","checksum":"546c1b291d545e7b24aaaf4199dac671"}],"language":[{"iso":"eng"}],"page":"29","date_published":"2015-02-19T00:00:00Z","related_material":{"record":[{"status":"public","id":"5421","relation":"earlier_version"},{"status":"public","id":"5440","relation":"later_version"}]},"doi":"10.15479/AT:IST-2015-323-v1-1","date_created":"2018-12-12T11:39:18Z","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. \r\nThe vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. \r\nOur main results are:\r\n(1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure).\r\n(2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.\r\n"}],"oa_version":"Published Version","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"month":"02","citation":{"chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v1-1.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p.","mla":"Chatterjee, Krishnendu, et al. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v1-1.","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, The complexity of evolutionary games on graphs. IST Austria, 2015.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. The Complexity of Evolutionary Games on Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v1-1","apa":"Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015). The complexity of evolutionary games on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v1-1"},"date_updated":"2023-02-23T12:26:33Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["005","576"],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"title":"The complexity of evolutionary games on graphs","file_date_updated":"2020-07-14T12:46:53Z","department":[{"_id":"KrCh"}],"_id":"5432","type":"technical_report","status":"public","pubrep_id":"323"},{"status":"public","pubrep_id":"399","type":"technical_report","_id":"5444","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:58Z","title":"Reconstructing robust phylogenies of metastatic cancers","author":[{"last_name":"Reiter","full_name":"Reiter, Johannes","orcid":"0000-0002-0170-7353","first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Makohon-Moore, Alvin","last_name":"Makohon-Moore","first_name":"Alvin"},{"first_name":"Jeffrey","full_name":"Gerold, Jeffrey","last_name":"Gerold"},{"first_name":"Ivana","last_name":"Bozic","full_name":"Bozic, Ivana"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Iacobuzio-Donahue","full_name":"Iacobuzio-Donahue, Christine","first_name":"Christine"},{"last_name":"Vogelstein","full_name":"Vogelstein, Bert","first_name":"Bert"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"}],"ddc":["000","576"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Reiter J, Makohon-Moore A, Gerold J, Bozic I, Chatterjee K, Iacobuzio-Donahue C, Vogelstein B, Nowak M. 2015. Reconstructing robust phylogenies of metastatic cancers, IST Austria, 25p.","chicago":"Reiter, Johannes, Alvin Makohon-Moore, Jeffrey Gerold, Ivana Bozic, Krishnendu Chatterjee, Christine Iacobuzio-Donahue, Bert Vogelstein, and Martin Nowak. Reconstructing Robust Phylogenies of Metastatic Cancers. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-399-v1-1.","ieee":"J. Reiter et al., Reconstructing robust phylogenies of metastatic cancers. IST Austria, 2015.","short":"J. Reiter, A. Makohon-Moore, J. Gerold, I. Bozic, K. Chatterjee, C. Iacobuzio-Donahue, B. Vogelstein, M. Nowak, Reconstructing Robust Phylogenies of Metastatic Cancers, IST Austria, 2015.","ama":"Reiter J, Makohon-Moore A, Gerold J, et al. Reconstructing Robust Phylogenies of Metastatic Cancers. IST Austria; 2015. doi:10.15479/AT:IST-2015-399-v1-1","apa":"Reiter, J., Makohon-Moore, A., Gerold, J., Bozic, I., Chatterjee, K., Iacobuzio-Donahue, C., … Nowak, M. (2015). Reconstructing robust phylogenies of metastatic cancers. IST Austria. https://doi.org/10.15479/AT:IST-2015-399-v1-1","mla":"Reiter, Johannes, et al. Reconstructing Robust Phylogenies of Metastatic Cancers. IST Austria, 2015, doi:10.15479/AT:IST-2015-399-v1-1."},"date_updated":"2020-07-14T23:05:07Z","month":"12","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal."}],"date_published":"2015-12-30T00:00:00Z","doi":"10.15479/AT:IST-2015-399-v1-1","date_created":"2018-12-12T11:39:22Z","page":"25","day":"30","file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"c47d33bdda06181753c0af36f16e7b5d","file_id":"5485","file_size":3533200,"date_updated":"2020-07-14T12:46:58Z","creator":"system","file_name":"IST-2015-399-v1+1_treeomics.pdf","date_created":"2018-12-12T11:53:24Z"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","publication_status":"published","year":"2015"}]