[{"abstract":[{"lang":"eng","text":"DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results."}],"oa_version":"Published Version","oa":1,"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"month":"02","publication_status":"published","year":"2015","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:46:53Z","file_size":378162,"creator":"system","date_created":"2018-12-12T11:53:14Z","file_name":"IST-2015-326-v1+1_main.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5475","checksum":"8542fd0b10aed7811cd41077b8ccb632"},{"content_type":"text/plain","relation":"main_file","access_level":"closed","checksum":"84c31c537bdaf7a91909f18d25d640ab","file_id":"6317","file_size":64,"date_updated":"2020-07-14T12:46:53Z","creator":"dernst","file_name":"IST-2015-326-v1+2_authors.txt","date_created":"2019-04-16T13:00:33Z"}],"day":"19","page":"16","date_created":"2018-12-12T11:39:18Z","date_published":"2015-02-19T00:00:00Z","_id":"5434","type":"technical_report","pubrep_id":"326","status":"public","citation":{"chicago":"Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria, 2015.","ista":"Anonymous 1, Anonymous 2. 2015. Optimal cost indefinite-horizon reachability in goal DEC-POMDPs, IST Austria, 16p.","mla":"Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria, 2015.","short":"1 Anonymous, 2 Anonymous, Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs, IST Austria, 2015.","ieee":"1 Anonymous and 2 Anonymous, Optimal cost indefinite-horizon reachability in goal DEC-POMDPs. IST Austria, 2015.","ama":"Anonymous 1, Anonymous 2. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria; 2015.","apa":"Anonymous, 1, & Anonymous, 2. (2015). Optimal cost indefinite-horizon reachability in goal DEC-POMDPs. IST Austria."},"date_updated":"2020-07-14T23:04:59Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"author":[{"first_name":"1","last_name":"Anonymous","full_name":"Anonymous, 1"},{"first_name":"2","full_name":"Anonymous, 2","last_name":"Anonymous"}],"file_date_updated":"2020-07-14T12:46:53Z","title":"Optimal cost indefinite-horizon reachability in goal DEC-POMDPs"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IEEE, 2015, pp. 244–56, doi:10.1109/LICS.2015.32.","ieee":"K. Chatterjee, Z. Komárková, and J. Kretinsky, “Unifying two views on multiple mean-payoff objectives in Markov decision processes.” IEEE, pp. 244–256, 2015.","short":"K. Chatterjee, Z. Komárková, J. Kretinsky, (2015) 244–256.","ama":"Chatterjee K, Komárková Z, Kretinsky J. Unifying two views on multiple mean-payoff objectives in Markov decision processes. 2015:244-256. doi:10.1109/LICS.2015.32","apa":"Chatterjee, K., Komárková, Z., & Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. Presented at the LICS: Logic in Computer Science, Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.32","chicago":"Chatterjee, Krishnendu, Zuzana Komárková, and Jan Kretinsky. “Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes.” LICS. IEEE, 2015. https://doi.org/10.1109/LICS.2015.32.","ista":"Chatterjee K, Komárková Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes. , 244–256."},"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Komárková","full_name":"Komárková, Zuzana","first_name":"Zuzana"},{"last_name":"Kretinsky","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"publist_id":"5493","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"day":"01","year":"2015","date_published":"2015-07-01T00:00:00Z","doi":"10.1109/LICS.2015.32","date_created":"2018-12-11T11:53:18Z","page":"244 - 256","acknowledgement":"A Technical Report of this paper is available at: https://repository.ist.ac.at/327\r\n","publisher":"IEEE","quality_controlled":"1","date_updated":"2023-02-23T12:26:16Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"series_title":"LICS","_id":"1657","status":"public","type":"conference","conference":{"start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan","name":"LICS: Logic in Computer Science"},"language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"relation":"later_version","status":"public","id":"466"},{"status":"public","id":"5429","relation":"earlier_version"},{"relation":"earlier_version","status":"public","id":"5435"}]},"ec_funded":1,"oa_version":"None","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i) ~the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) ~the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., Ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems, which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem. "}],"month":"07","scopus_import":1,"alternative_title":["LICS"]},{"conference":{"location":"Kyoto, Japan","end_date":"2015-07-10","start_date":"2015-07-06","name":"LICS: Logic in Computer Science"},"type":"conference","status":"public","_id":"1656","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_updated":"2023-02-23T12:26:19Z","scopus_import":1,"month":"07","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. In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties."}],"oa_version":"None","ec_funded":1,"volume":"2015-July","related_material":{"record":[{"status":"public","id":"467","relation":"later_version"},{"id":"5415","status":"public","relation":"earlier_version"},{"relation":"earlier_version","id":"5436","status":"public"}]},"publication_status":"published","language":[{"iso":"eng"}],"project":[{"grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z211","name":"The Wittgenstein Prize"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"article_number":"7174926","external_id":{"arxiv":["1606.03598"]},"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","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","full_name":"Otop, Jan"}],"publist_id":"5494","title":"Nested weighted automata","citation":{"mla":"Chatterjee, Krishnendu, et al. “Nested Weighted Automata.” Proceedings - Symposium on Logic in Computer Science, vol. 2015–July, 7174926, IEEE, 2015, doi:10.1109/LICS.2015.72.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Nested weighted automata,” in Proceedings - Symposium on Logic in Computer Science, Kyoto, Japan, 2015, vol. 2015–July.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). Nested weighted automata. In Proceedings - Symposium on Logic in Computer Science (Vol. 2015–July). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.72","ama":"Chatterjee K, Henzinger TA, Otop J. Nested weighted automata. In: Proceedings - Symposium on Logic in Computer Science. Vol 2015-July. IEEE; 2015. doi:10.1109/LICS.2015.72","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Nested Weighted Automata.” In Proceedings - Symposium on Logic in Computer Science, Vol. 2015–July. IEEE, 2015. https://doi.org/10.1109/LICS.2015.72.","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174926."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IEEE","quality_controlled":"1","acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23 (RiSE), Z211-N23 (Wittgenstein Award), FWF Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nA Technical Report of the paper is available at: \r\nhttps://repository.ist.ac.at/331/\r\n","date_created":"2018-12-11T11:53:17Z","doi":"10.1109/LICS.2015.72","date_published":"2015-07-31T00:00:00Z","year":"2015","publication":"Proceedings - Symposium on Logic in Computer Science","day":"31"},{"oa":1,"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"month":"01","abstract":[{"text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.\r\nOur problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.\r\nFinally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.","lang":"eng"}],"oa_version":"Published Version","page":"41","date_created":"2018-12-12T11:39:17Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"1657"},{"id":"466","status":"public","relation":"later_version"},{"relation":"later_version","status":"public","id":"5435"}]},"doi":"10.15479/AT:IST-2015-318-v1-1","date_published":"2015-01-12T00:00:00Z","publication_status":"published","year":"2015","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"language":[{"iso":"eng"}],"file":[{"file_size":689863,"date_updated":"2020-07-14T12:46:52Z","creator":"system","file_name":"IST-2015-318-v1+1_main.pdf","date_created":"2018-12-12T11:54:11Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"5533","checksum":"e4869a584567c506349abda9c8ec7db3"}],"day":"12","type":"technical_report","pubrep_id":"318","status":"public","_id":"5429","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Zuzana","full_name":"Komarkova, Zuzana","last_name":"Komarkova"},{"last_name":"Kretinsky","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"}],"department":[{"_id":"KrCh"}],"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","file_date_updated":"2020-07-14T12:46:52Z","citation":{"chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v1-1.","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","mla":"Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v1-1.","apa":"Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2015-318-v1-1","ama":"Chatterjee K, Komarkova Z, Kretinsky J. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v1-1","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria, 2015.","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015."},"date_updated":"2023-02-23T12:26:16Z","ddc":["004"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP.\r\nWe also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem."}],"oa_version":"Published Version","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa":1,"month":"02","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","year":"2015","publication_status":"published","day":"23","file":[{"creator":"system","file_size":717630,"date_updated":"2020-07-14T12:46:53Z","file_name":"IST-2015-318-v2+1_main.pdf","date_created":"2018-12-12T11:54:03Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"5525","checksum":"75284adec80baabdfe71ff9ebbc27445"}],"language":[{"iso":"eng"}],"page":"51","doi":"10.15479/AT:IST-2015-318-v2-1","date_published":"2015-02-23T00:00:00Z","related_material":{"record":[{"status":"public","id":"1657","relation":"later_version"},{"id":"466","status":"public","relation":"later_version"},{"id":"5429","status":"public","relation":"earlier_version"}]},"date_created":"2018-12-12T11:39:19Z","_id":"5435","type":"technical_report","status":"public","pubrep_id":"327","date_updated":"2023-02-23T12:26:00Z","citation":{"ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 51p.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v2-1.","apa":"Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2015-318-v2-1","ama":"Chatterjee K, Komarkova Z, Kretinsky J. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v2-1","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria, 2015.","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v2-1."},"ddc":["004"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Komarkova","full_name":"Komarkova, Zuzana","first_name":"Zuzana"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Kretinsky","full_name":"Kretinsky, Jan","orcid":"0000-0002-8122-2881"}],"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:53Z"},{"oa_version":"Published Version","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"}],"month":"04","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa":1,"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5541","checksum":"3c402f47d3669c28d04d1af405a08e3f","creator":"system","date_updated":"2020-07-14T12:46:54Z","file_size":569991,"date_created":"2018-12-12T11:54:19Z","file_name":"IST-2015-170-v2+2_report.pdf"}],"day":"24","language":[{"iso":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"publication_status":"published","year":"2015","related_material":{"record":[{"relation":"later_version","status":"public","id":"1656"},{"id":"467","status":"public","relation":"later_version"},{"relation":"earlier_version","status":"public","id":"5415"}]},"date_published":"2015-04-24T00:00:00Z","doi":"10.15479/AT:IST-2015-170-v2-2","date_created":"2018-12-12T11:39:19Z","page":"29","_id":"5436","status":"public","pubrep_id":"331","type":"technical_report","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, et al. 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","ama":"Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria; 2015. doi: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","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Nested weighted automata","file_date_updated":"2020-07-14T12:46:54Z","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","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"}]},{"citation":{"short":"U. Boker, T.A. Henzinger, J. Otop, in:, LICS, IEEE, 2015, pp. 750–761.","ieee":"U. Boker, T. A. Henzinger, and J. Otop, “The target discounted-sum problem,” in LICS, Kyoto, Japan, 2015, pp. 750–761.","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","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","mla":"Boker, Udi, et al. “The Target Discounted-Sum Problem.” LICS, IEEE, 2015, pp. 750–61, doi:10.1109/LICS.2015.74.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","full_name":"Boker, Udi","last_name":"Boker"},{"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"}],"publist_id":"5491","article_processing_charge":"No","title":"The target discounted-sum problem","project":[{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"has_accepted_license":"1","year":"2015","day":"01","publication":"LICS","page":"750 - 761","doi":"10.1109/LICS.2015.74","date_published":"2015-07-01T00:00:00Z","date_created":"2018-12-11T11:53:19Z","acknowledgement":"A technical report of the article is available at: https://research-explorer.app.ist.ac.at/record/5439","quality_controlled":"1","publisher":"IEEE","oa":1,"date_updated":"2023-02-23T12:26:27Z","ddc":["000"],"department":[{"_id":"ToHe"}],"file_date_updated":"2020-07-14T12:45:10Z","_id":"1659","series_title":"Logic in Computer Science","type":"conference","conference":{"name":"LICS: Logic in Computer Science","start_date":"2015-007-06","end_date":"2015-07-10","location":"Kyoto, Japan"},"status":"public","publication_identifier":{"eisbn":["978-1-4799-8875-4 "],"issn":["1043-6871 "]},"publication_status":"published","file":[{"date_created":"2020-05-15T08:53:29Z","file_name":"2015_LICS_Boker.pdf","creator":"dernst","date_updated":"2020-07-14T12:45:10Z","file_size":340215,"checksum":"6abebca9c1a620e9e103a8f9222befac","file_id":"7852","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5439"}]},"ec_funded":1,"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":"Submitted Version","scopus_import":1,"month":"07"},{"citation":{"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.","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.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International Colloquium, Springer Nature, 2015, 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."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publist_id":"5556","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop"}],"external_id":{"arxiv":["1504.08259"]},"article_processing_charge":"No","title":"Edit distance for pushdown automata","project":[{"grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"name":"The Wittgenstein Prize","grant_number":"Z211","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407","name":"Game Theory"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"year":"2015","day":"01","publication":"42nd International Colloquium","page":"121 - 133","doi":"10.1007/978-3-662-47666-6_10","date_published":"2015-07-01T00:00:00Z","date_created":"2018-12-11T11:53:01Z","publisher":"Springer Nature","quality_controlled":"1","oa":1,"date_updated":"2023-02-23T12:26:24Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"_id":"1610","type":"conference","conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"2015-07-06","location":"Kyoto, Japan","end_date":"2015-07-10"},"status":"public","pubrep_id":"321","publication_identifier":{"isbn":["978-3-662-47665-9"]},"publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"465","relation":"later_version"},{"status":"public","id":"5438","relation":"earlier_version"}]},"volume":9135,"issue":"Part II","ec_funded":1,"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."}],"oa_version":"None","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1504.08259"}],"month":"07","intvolume":" 9135"},{"_id":"5437","type":"technical_report","status":"public","pubrep_id":"333","date_updated":"2023-02-23T12:26:05Z","citation":{"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.","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.","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","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."},"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"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis"}],"file_date_updated":"2020-07-14T12:46:54Z","department":[{"_id":"KrCh"}],"title":"Faster algorithms for quantitative verification in constant treewidth graphs","abstract":[{"text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. \r\nThe algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.\r\nOur main theoretical results are as follows.\r\nFirst, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when the output is $\\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$ and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. ","lang":"eng"}],"oa_version":"Published Version","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa":1,"month":"04","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","year":"2015","publication_status":"published","file":[{"file_id":"5473","checksum":"f5917c20f84018b362d385c000a2e123","content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T11:53:12Z","file_name":"IST-2015-330-v2+1_main.pdf","date_updated":"2020-07-14T12:46:54Z","file_size":1072137,"creator":"system"}],"day":"27","language":[{"iso":"eng"}],"page":"27","related_material":{"record":[{"relation":"later_version","id":"1607","status":"public"},{"status":"public","id":"5430","relation":"earlier_version"}]},"date_published":"2015-04-27T00:00:00Z","doi":"10.15479/AT:IST-2015-330-v2-1","date_created":"2018-12-12T11:39:19Z"},{"abstract":[{"text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. 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.","lang":"eng"}],"oa_version":"Published Version","oa":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","month":"02","year":"2015","publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","language":[{"iso":"eng"}],"day":"10","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"5482","checksum":"62c6ea01e342553dcafb88a070fb1ad5","creator":"system","date_updated":"2020-07-14T12:46:52Z","file_size":1089651,"date_created":"2018-12-12T11:53:21Z","file_name":"IST-2015-319-v1+1_long.pdf"}],"page":"31","date_created":"2018-12-12T11:39:17Z","doi":"10.15479/AT:IST-2015-319-v1-1","related_material":{"record":[{"id":"1607","status":"public","relation":"later_version"},{"relation":"later_version","status":"public","id":"5437"}]},"date_published":"2015-02-10T00:00:00Z","_id":"5430","type":"technical_report","pubrep_id":"319","status":"public","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","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"title":"Faster algorithms for quantitative verification in constant treewidth graphs","file_date_updated":"2020-07-14T12:46:52Z","department":[{"_id":"KrCh"}]}]