--- _id: '2213' abstract: - lang: eng text: We consider two-player partial-observation stochastic games on finitestate graphs where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are ε-regular conditions specified as parity objectives. The qualitative-analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). These qualitative-analysis problems are known to be undecidable. However in many applications the relevant question is the existence of finite-memory strategies, and the qualitative-analysis problems under finite-memory strategies was recently shown to be decidable in 2EXPTIME.We improve the complexity and show that the qualitative-analysis problems for partial-observation stochastic parity games under finite-memory strategies are EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. acknowledgement: 'This research was supported by European project Cassting (FP7-601148), NSF grants CNS 1049862 and CCF-1139011, by NSF Expe ditions in Computing project “ExCAPE: Expeditions in Computer Augmented Program Engineering”, by BSF grant 9800096, and by gift from Intel.' alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen - first_name: Sumit full_name: Nain, Sumit last_name: Nain - first_name: Moshe full_name: Vardi, Moshe last_name: Vardi citation: ama: 'Chatterjee K, Doyen L, Nain S, Vardi M. The complexity of partial-observation stochastic parity games with finite-memory strategies. In: Vol 8412. Springer; 2014:242-257. doi:10.1007/978-3-642-54830-7_16' apa: 'Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2014). The complexity of partial-observation stochastic parity games with finite-memory strategies (Vol. 8412, pp. 242–257). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. https://doi.org/10.1007/978-3-642-54830-7_16' chicago: Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. “The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies,” 8412:242–57. Springer, 2014. https://doi.org/10.1007/978-3-642-54830-7_16. ieee: 'K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, “The complexity of partial-observation stochastic parity games with finite-memory strategies,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 242–257.' ista: 'Chatterjee K, Doyen L, Nain S, Vardi M. 2014. The complexity of partial-observation stochastic parity games with finite-memory strategies. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 242–257.' mla: Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. Vol. 8412, Springer, 2014, pp. 242–57, doi:10.1007/978-3-642-54830-7_16. short: K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257. conference: end_date: 2014-04-13 location: Grenoble, France name: 'FoSSaCS: Foundations of Software Science and Computation Structures' start_date: 2014-04-05 date_created: 2018-12-11T11:56:21Z date_published: 2014-04-01T00:00:00Z date_updated: 2023-02-23T12:24:58Z day: '01' department: - _id: KrCh doi: 10.1007/978-3-642-54830-7_16 ec_funded: 1 external_id: arxiv: - '1401.3289' intvolume: ' 8412' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1401.3289 month: '04' oa: 1 oa_version: Preprint page: 242 - 257 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication_status: published publisher: Springer publist_id: '4757' quality_controlled: '1' related_material: record: - id: '5408' relation: earlier_version status: public scopus_import: 1 status: public title: The complexity of partial-observation stochastic parity games with finite-memory strategies type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8412 year: '2014' ... --- _id: '2212' abstract: - lang: eng text: 'The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2 1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2 1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic). We present an algorithm running in time O(d·n2d·MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2 1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective). ' acknowledgement: "This research was supported by European project Cassting (FP7-601148).\r\nA Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/128." alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen - first_name: Hugo full_name: Gimbert, Hugo last_name: Gimbert - first_name: Youssouf full_name: Oualhadj, Youssouf last_name: Oualhadj citation: ama: 'Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-information stochastic mean-payoff parity games. In: Vol 8412. Springer; 2014:210-225. doi:10.1007/978-3-642-54830-7_14' apa: 'Chatterjee, K., Doyen, L., Gimbert, H., & Oualhadj, Y. (2014). Perfect-information stochastic mean-payoff parity games (Vol. 8412, pp. 210–225). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. https://doi.org/10.1007/978-3-642-54830-7_14' chicago: Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. “Perfect-Information Stochastic Mean-Payoff Parity Games,” 8412:210–25. Springer, 2014. https://doi.org/10.1007/978-3-642-54830-7_14. ieee: 'K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, “Perfect-information stochastic mean-payoff parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 210–225.' ista: 'Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2014. Perfect-information stochastic mean-payoff parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 210–225.' mla: Chatterjee, Krishnendu, et al. Perfect-Information Stochastic Mean-Payoff Parity Games. Vol. 8412, Springer, 2014, pp. 210–25, doi:10.1007/978-3-642-54830-7_14. short: K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, in:, Springer, 2014, pp. 210–225. conference: end_date: 2014-04-13 location: Grenoble, France name: 'FoSSaCS: Foundations of Software Science and Computation Structures' start_date: 2014-04-05 date_created: 2018-12-11T11:56:21Z date_published: 2014-04-01T00:00:00Z date_updated: 2023-02-23T12:24:50Z day: '01' department: - _id: KrCh doi: 10.1007/978-3-642-54830-7_14 ec_funded: 1 intvolume: ' 8412' language: - iso: eng month: '04' oa_version: None page: 210 - 225 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication_status: published publisher: Springer publist_id: '4758' quality_controlled: '1' related_material: record: - id: '5405' relation: earlier_version status: public scopus_import: 1 status: public title: Perfect-information stochastic mean-payoff parity games type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8412 year: '2014' ... --- _id: '2216' abstract: - lang: eng text: The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in time stamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than δ away from the parameter, for δ > 0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and analogous decidability results hold for rectangular automata. author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Ritankar full_name: Majumdar, Ritankar last_name: Majumdar citation: ama: 'Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit distance for timed automata. In: Springer; 2014:303-312. doi:10.1145/2562059.2562141' apa: 'Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2014). Edit distance for timed automata (pp. 303–312). Presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany: Springer. https://doi.org/10.1145/2562059.2562141' chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Ritankar Majumdar. “Edit Distance for Timed Automata,” 303–12. Springer, 2014. https://doi.org/10.1145/2562059.2562141. ieee: 'K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, “Edit distance for timed automata,” presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany, 2014, pp. 303–312.' ista: 'Chatterjee K, Ibsen-Jensen R, Majumdar R. 2014. Edit distance for timed automata. HSCC: Hybrid Systems - Computation and Control, 303–312.' mla: Chatterjee, Krishnendu, et al. Edit Distance for Timed Automata. Springer, 2014, pp. 303–12, doi:10.1145/2562059.2562141. short: K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, in:, Springer, 2014, pp. 303–312. conference: end_date: 2017-04-17 location: Berlin, Germany name: 'HSCC: Hybrid Systems - Computation and Control' start_date: 2017-04-15 date_created: 2018-12-11T11:56:22Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T12:25:01Z day: '01' department: - _id: KrCh doi: 10.1145/2562059.2562141 language: - iso: eng main_file_link: - open_access: '1' url: https://dl.acm.org/citation.cfm?doid=2562059.2562141 month: '01' oa: 1 oa_version: Submitted Version page: 303 - 312 publication_status: published publisher: Springer publist_id: '4752' quality_controlled: '1' related_material: record: - id: '5409' relation: earlier_version status: public status: public title: Edit distance for timed automata type: conference user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5411' abstract: - lang: eng text: "Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing.\r\nIn this paper, we study compositional properties of the IOCO-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the IOCO conformance relation, the resulting methodology can be applied to a broader class of systems." alternative_title: - IST Austria Technical Report author: - first_name: Przemyslaw full_name: Daca, Przemyslaw id: 49351290-F248-11E8-B48F-1D18A9856A87 last_name: Daca - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Willibald full_name: Krenn, Willibald last_name: Krenn - first_name: Dejan full_name: Nickovic, Dejan id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87 last_name: Nickovic citation: ama: Daca P, Henzinger TA, Krenn W, Nickovic D. Compositional Specifications for IOCO Testing. IST Austria; 2014. doi:10.15479/AT:IST-2014-148-v2-1 apa: Daca, P., Henzinger, T. A., Krenn, W., & Nickovic, D. (2014). Compositional specifications for IOCO testing. IST Austria. https://doi.org/10.15479/AT:IST-2014-148-v2-1 chicago: Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic. Compositional Specifications for IOCO Testing. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-148-v2-1. ieee: P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, Compositional specifications for IOCO testing. IST Austria, 2014. ista: Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications for IOCO testing, IST Austria, 20p. mla: Daca, Przemyslaw, et al. Compositional Specifications for IOCO Testing. IST Austria, 2014, doi:10.15479/AT:IST-2014-148-v2-1. short: P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, Compositional Specifications for IOCO Testing, IST Austria, 2014. date_created: 2018-12-12T11:39:11Z date_published: 2014-01-28T00:00:00Z date_updated: 2023-02-23T10:31:07Z day: '28' ddc: - '000' department: - _id: ToHe doi: 10.15479/AT:IST-2014-148-v2-1 file: - access_level: open_access checksum: 0e03aba625cc334141a3148432aa5760 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:21Z date_updated: 2020-07-14T12:46:46Z file_id: '5543' file_name: IST-2014-148-v2+1_main_tr.pdf file_size: 534732 relation: main_file file_date_updated: 2020-07-14T12:46:46Z has_accepted_license: '1' language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: '20' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '152' related_material: record: - id: '2167' relation: later_version status: public status: public title: Compositional specifications for IOCO testing type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5413' abstract: - lang: eng text: "We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. " alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Przemyslaw full_name: Daca, Przemyslaw id: 49351290-F248-11E8-B48F-1D18A9856A87 last_name: Daca - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik citation: ama: Chatterjee K, Daca P, Chmelik M. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v2-2 apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). CEGAR for qualitative analysis of probabilistic systems. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v2-2 chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v2-2. ieee: K. Chatterjee, P. Daca, and M. Chmelik, CEGAR for qualitative analysis of probabilistic systems. IST Austria, 2014. ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p. mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v2-2. short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014. date_created: 2018-12-12T11:39:11Z date_published: 2014-02-06T00:00:00Z date_updated: 2023-02-23T12:25:18Z day: '06' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2014-153-v2-2 file: - access_level: open_access checksum: ce4967a184d84863eec76c66cbac1614 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:17Z date_updated: 2020-07-14T12:46:47Z file_id: '5539' file_name: IST-2014-153-v2+2_main.pdf file_size: 606049 relation: main_file file_date_updated: 2020-07-14T12:46:47Z has_accepted_license: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: '33' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '164' related_material: record: - id: '2063' relation: later_version status: public - id: '5412' relation: earlier_version status: public - id: '5414' relation: later_version status: public status: public title: CEGAR for qualitative analysis of probabilistic systems type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5414' abstract: - lang: eng text: "We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. " alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Przemyslaw full_name: Daca, Przemyslaw id: 49351290-F248-11E8-B48F-1D18A9856A87 last_name: Daca - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik citation: ama: Chatterjee K, Daca P, Chmelik M. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v3-1 apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). CEGAR for qualitative analysis of probabilistic systems. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v3-1 chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v3-1. ieee: K. Chatterjee, P. Daca, and M. Chmelik, CEGAR for qualitative analysis of probabilistic systems. IST Austria, 2014. ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p. mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v3-1. short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014. date_created: 2018-12-12T11:39:12Z date_published: 2014-02-07T00:00:00Z date_updated: 2023-02-23T12:25:15Z day: '07' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2014-153-v3-1 file: - access_level: open_access checksum: 87b93fe9af71fc5c94b0eb6151537e11 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:03Z date_updated: 2020-07-14T12:46:48Z file_id: '5464' file_name: IST-2014-153-v3+1_main.pdf file_size: 606227 relation: main_file file_date_updated: 2020-07-14T12:46:48Z has_accepted_license: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: '33' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '165' related_material: record: - id: '2063' relation: later_version status: public - id: '5412' relation: earlier_version status: public - id: '5413' relation: earlier_version status: public status: public title: CEGAR for qualitative analysis of probabilistic systems type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5412' abstract: - lang: eng text: "We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. " alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Przemyslaw full_name: Daca, Przemyslaw id: 49351290-F248-11E8-B48F-1D18A9856A87 last_name: Daca - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik citation: ama: Chatterjee K, Daca P, Chmelik M. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v1-1 apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). CEGAR for qualitative analysis of probabilistic systems. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v1-1 chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v1-1. ieee: K. Chatterjee, P. Daca, and M. Chmelik, CEGAR for qualitative analysis of probabilistic systems. IST Austria, 2014. ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 31p. mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v1-1. short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014. date_created: 2018-12-12T11:39:11Z date_published: 2014-01-29T00:00:00Z date_updated: 2023-02-23T12:25:18Z day: '29' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2014-153-v1-1 file: - access_level: open_access checksum: 4d6cda4bebed970926403ad6ad8c745f content_type: application/pdf creator: system date_created: 2018-12-12T11:53:39Z date_updated: 2020-07-14T12:46:47Z file_id: '5500' file_name: IST-2014-153-v1+1_main.pdf file_size: 423322 relation: main_file file_date_updated: 2020-07-14T12:46:47Z has_accepted_license: '1' language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: '31' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '153' related_material: record: - id: '2063' relation: later_version status: public - id: '5413' relation: later_version status: public - id: '5414' relation: later_version status: public status: public title: CEGAR for qualitative analysis of probabilistic systems type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '2163' abstract: - lang: eng text: We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable in general, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games. acknowledgement: "This research was partly supported by European project Cassting (FP7-601148).\r\nTechnical Report under https://research-explorer.app.ist.ac.at/record/5418\r\n" alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen citation: ama: 'Chatterjee K, Doyen L. Games with a weak adversary. In: Lecture Notes in Computer Science. Vol 8573. Springer; 2014:110-121. doi:10.1007/978-3-662-43951-7_10' apa: 'Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. In Lecture Notes in Computer Science (Vol. 8573, pp. 110–121). Copenhagen, Denmark: Springer. https://doi.org/10.1007/978-3-662-43951-7_10' chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” In Lecture Notes in Computer Science, 8573:110–21. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7_10. ieee: K. Chatterjee and L. Doyen, “Games with a weak adversary,” in Lecture Notes in Computer Science, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 110–121. ista: 'Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573, 110–121.' mla: Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” Lecture Notes in Computer Science, vol. 8573, no. Part 2, Springer, 2014, pp. 110–21, doi:10.1007/978-3-662-43951-7_10. short: K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121. conference: end_date: 2014-07-11 location: Copenhagen, Denmark name: 'ICALP: Automata, Languages and Programming' start_date: 2014-07-08 date_created: 2018-12-11T11:56:04Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T12:25:29Z day: '01' department: - _id: KrCh doi: 10.1007/978-3-662-43951-7_10 ec_funded: 1 external_id: arxiv: - '1404.5453' intvolume: ' 8573' issue: Part 2 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1404.5453 month: '01' oa: 1 oa_version: Preprint page: 110 - 121 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: Lecture Notes in Computer Science publication_status: published publisher: Springer publist_id: '4821' quality_controlled: '1' related_material: record: - id: '5418' relation: earlier_version status: public status: public title: Games with a weak adversary type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8573 year: '2014' ... --- _id: '5419' abstract: - lang: eng text: "We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:\r\n1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).\r\n2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.\r\nOur algorithms improve all existing results, and use very simple data structures." alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: ama: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs. IST Austria; 2014. doi:10.15479/AT:IST-2014-187-v1-1 apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2014). Improved algorithms for reachability and shortest path on low tree-width graphs. IST Austria. https://doi.org/10.15479/AT:IST-2014-187-v1-1 chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-187-v1-1. ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Improved algorithms for reachability and shortest path on low tree-width graphs. IST Austria, 2014. ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for reachability and shortest path on low tree-width graphs, IST Austria, 34p. mla: Chatterjee, Krishnendu, et al. Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs. IST Austria, 2014, doi:10.15479/AT:IST-2014-187-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014. date_created: 2018-12-12T11:39:13Z date_published: 2014-04-14T00:00:00Z date_updated: 2021-01-12T08:02:03Z day: '14' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2014-187-v1-1 file: - access_level: open_access checksum: c608e66030a4bf51d2d99b451f539b99 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:25Z date_updated: 2020-07-14T12:46:50Z file_id: '5548' file_name: IST-2014-187-v1+1_main_full_tech.pdf file_size: 670031 relation: main_file file_date_updated: 2020-07-14T12:46:50Z has_accepted_license: '1' language: - iso: eng month: '04' oa: 1 oa_version: Published Version page: '34' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '187' status: public title: Improved algorithms for reachability and shortest path on low tree-width graphs type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '2217' abstract: - lang: eng text: "As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.\r\n\r\nThe contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem." acknowledgement: "This work was supported in part by the Austrian Science Fund NFN RiSE (Rigorous Systems Engineering) and by the ERC Advanced Grant QUAREM (Quantitative Reactive Modeling).\r\nA Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/171" article_processing_charge: No author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop citation: ama: 'Henzinger TA, Otop J. Model measuring for hybrid systems. In: Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control. Springer; 2014:213-222. doi:10.1145/2562059.2562130' apa: 'Henzinger, T. A., & Otop, J. (2014). Model measuring for hybrid systems. In Proceedings of the 17th international conference on Hybrid systems: computation and control (pp. 213–222). Berlin, Germany: Springer. https://doi.org/10.1145/2562059.2562130' chicago: 'Henzinger, Thomas A, and Jan Otop. “Model Measuring for Hybrid Systems.” In Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control, 213–22. Springer, 2014. https://doi.org/10.1145/2562059.2562130.' ieee: 'T. A. Henzinger and J. Otop, “Model measuring for hybrid systems,” in Proceedings of the 17th international conference on Hybrid systems: computation and control, Berlin, Germany, 2014, pp. 213–222.' ista: 'Henzinger TA, Otop J. 2014. Model measuring for hybrid systems. Proceedings of the 17th international conference on Hybrid systems: computation and control. HSCC: Hybrid Systems - Computation and Control, 213–222.' mla: 'Henzinger, Thomas A., and Jan Otop. “Model Measuring for Hybrid Systems.” Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control, Springer, 2014, pp. 213–22, doi:10.1145/2562059.2562130.' short: 'T.A. Henzinger, J. Otop, in:, Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control, Springer, 2014, pp. 213–222.' conference: end_date: 2014-04-17 location: Berlin, Germany name: 'HSCC: Hybrid Systems - Computation and Control' start_date: 2014-04-15 date_created: 2018-12-11T11:56:23Z date_published: 2014-04-01T00:00:00Z date_updated: 2023-02-23T12:25:23Z day: '01' department: - _id: ToHe doi: 10.1145/2562059.2562130 ec_funded: 1 language: - iso: eng month: '04' oa_version: None page: 213 - 222 project: - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering publication: 'Proceedings of the 17th international conference on Hybrid systems: computation and control' publication_status: published publisher: Springer publist_id: '4751' quality_controlled: '1' related_material: record: - id: '5416' relation: earlier_version status: public scopus_import: 1 status: public title: Model measuring for hybrid systems type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5417' abstract: - lang: eng text: "We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.\r\nThe model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.\r\nWe show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.\r\nWe use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. \r\nWe give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications." alternative_title: - IST Austria Technical Report author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop citation: ama: Henzinger TA, Otop J. From Model Checking to Model Measuring. IST Austria; 2014. doi:10.15479/AT:IST-2014-172-v1-1 apa: Henzinger, T. A., & Otop, J. (2014). From model checking to model measuring. IST Austria. https://doi.org/10.15479/AT:IST-2014-172-v1-1 chicago: Henzinger, Thomas A, and Jan Otop. From Model Checking to Model Measuring. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-172-v1-1. ieee: T. A. Henzinger and J. Otop, From model checking to model measuring. IST Austria, 2014. ista: Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria, 14p. mla: Henzinger, Thomas A., and Jan Otop. From Model Checking to Model Measuring. IST Austria, 2014, doi:10.15479/AT:IST-2014-172-v1-1. short: T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria, 2014. date_created: 2018-12-12T11:39:13Z date_published: 2014-02-19T00:00:00Z date_updated: 2023-02-23T10:38:10Z day: '19' ddc: - '000' department: - _id: ToHe doi: 10.15479/AT:IST-2014-172-v1-1 file: - access_level: open_access checksum: fcc3eab903cfcd3778b338d2d0d44d18 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:20Z date_updated: 2020-07-14T12:46:49Z file_id: '5481' file_name: IST-2014-172-v1+1_report.pdf file_size: 383052 relation: main_file file_date_updated: 2020-07-14T12:46:49Z has_accepted_license: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: '14' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '175' related_material: record: - id: '2327' relation: later_version status: public status: public title: From model checking to model measuring type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5416' abstract: - lang: eng text: As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem. alternative_title: - IST Austria Technical Report author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop citation: ama: Henzinger TA, Otop J. Model Measuring for Hybrid Systems. IST Austria; 2014. doi:10.15479/AT:IST-2014-171-v1-1 apa: Henzinger, T. A., & Otop, J. (2014). Model measuring for hybrid systems. IST Austria. https://doi.org/10.15479/AT:IST-2014-171-v1-1 chicago: Henzinger, Thomas A, and Jan Otop. Model Measuring for Hybrid Systems. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-171-v1-1. ieee: T. A. Henzinger and J. Otop, Model measuring for hybrid systems. IST Austria, 2014. ista: Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria, 22p. mla: Henzinger, Thomas A., and Jan Otop. Model Measuring for Hybrid Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-171-v1-1. short: T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria, 2014. date_created: 2018-12-12T11:39:12Z date_published: 2014-02-19T00:00:00Z date_updated: 2023-02-23T10:33:21Z day: '19' ddc: - '005' department: - _id: ToHe doi: 10.15479/AT:IST-2014-171-v1-1 file: - access_level: open_access checksum: 445456d22371e4e49aad2b9a0c13bf80 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:32Z date_updated: 2020-07-14T12:46:49Z file_id: '5492' file_name: IST-2014-171-v1+1_report.pdf file_size: 712077 relation: main_file file_date_updated: 2020-07-14T12:46:49Z has_accepted_license: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: '22' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '171' related_material: record: - id: '2217' relation: later_version status: public status: public title: Model measuring for hybrid systems type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5418' abstract: - lang: eng text: We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results. alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen citation: ama: Chatterjee K, Doyen L. Games with a Weak Adversary. IST Austria; 2014. doi:10.15479/AT:IST-2014-176-v1-1 apa: Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. IST Austria. https://doi.org/10.15479/AT:IST-2014-176-v1-1 chicago: Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-176-v1-1. ieee: K. Chatterjee and L. Doyen, Games with a weak adversary. IST Austria, 2014. ista: Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p. mla: Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary. IST Austria, 2014, doi:10.15479/AT:IST-2014-176-v1-1. short: K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014. date_created: 2018-12-12T11:39:13Z date_published: 2014-03-22T00:00:00Z date_updated: 2023-02-23T10:30:58Z day: '22' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2014-176-v1-1 file: - access_level: open_access checksum: 1d6958aa60050e1c3e932c6e5f34c39f content_type: application/pdf creator: system date_created: 2018-12-12T11:53:07Z date_updated: 2020-07-14T12:46:49Z file_id: '5468' file_name: IST-2014-176-v1+1_icalp_14.pdf file_size: 328253 relation: main_file file_date_updated: 2020-07-14T12:46:49Z has_accepted_license: '1' language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: '18' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '176' related_material: record: - id: '2163' relation: later_version status: public status: public title: Games with a weak adversary type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5420' 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).' alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 citation: ama: Chatterjee K, Ibsen-Jensen R. The Value 1 Problem for Concurrent Mean-Payoff Games. IST Austria; 2014. doi:10.15479/AT:IST-2014-191-v1-1 apa: Chatterjee, K., & Ibsen-Jensen, R. (2014). The value 1 problem for concurrent mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2014-191-v1-1 chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem for Concurrent Mean-Payoff Games. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-191-v1-1. ieee: K. Chatterjee and R. Ibsen-Jensen, The value 1 problem for concurrent mean-payoff games. IST Austria, 2014. ista: Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p. mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem for Concurrent Mean-Payoff Games. IST Austria, 2014, doi:10.15479/AT:IST-2014-191-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff Games, IST Austria, 2014. date_created: 2018-12-12T11:39:14Z date_published: 2014-04-14T00:00:00Z date_updated: 2021-01-12T08:02:05Z day: '14' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2014-191-v1-1 file: - access_level: open_access checksum: 49e0fd3e62650346daf7dc04604f7a0a content_type: application/pdf creator: system date_created: 2018-12-12T11:53:58Z date_updated: 2020-07-14T12:46:50Z file_id: '5520' file_name: IST-2014-191-v1+1_main_full.pdf file_size: 584368 relation: main_file file_date_updated: 2020-07-14T12:46:50Z has_accepted_license: '1' language: - iso: eng month: '04' oa: 1 oa_version: Published Version page: '49' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '191' status: public title: The value 1 problem for concurrent mean-payoff games type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5422' abstract: - lang: eng text: Notes from the Third Plenary for the Research Data Alliance in Dublin, Ireland on March 26 to 28, 2014 with focus on starting an institutional research data repository. author: - first_name: Jana full_name: Porsche, Jana id: 3252EDC2-F248-11E8-B48F-1D18A9856A87 last_name: Porsche citation: ama: Porsche J. Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland. none; 2014. apa: Porsche, J. (2014). Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland. none. chicago: Porsche, Jana. Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland. none, 2014. ieee: J. Porsche, Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland. none, 2014. ista: Porsche J. 2014. Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland, none,p. mla: Porsche, Jana. Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland. none, 2014. short: J. Porsche, Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland, none, 2014. date_created: 2018-12-12T11:39:14Z date_published: 2014-01-01T00:00:00Z date_updated: 2020-07-14T23:04:56Z ddc: - '020' department: - _id: E-Lib file: - access_level: open_access checksum: 3954896648ce8afa8f7c4425e71cff08 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:40Z date_updated: 2020-07-14T12:46:50Z file_id: '5501' file_name: IST-2014-254-v1+1_Dublin_Day_3.pdf file_size: 648585 relation: main_file - access_level: open_access checksum: 9a0d42b0b832dfe7e4b22fb6816bcbba content_type: application/pdf creator: system date_created: 2018-12-12T11:53:41Z date_updated: 2020-07-14T12:46:50Z file_id: '5502' file_name: IST-2014-254-v1+2_Dublin_Day_1.pdf file_size: 221339 relation: main_file - access_level: open_access checksum: 498b8d629fb1bd17bff1dc43700a93e6 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:42Z date_updated: 2020-07-14T12:46:50Z file_id: '5503' file_name: IST-2014-254-v1+3_Dublin_Day_2.pdf file_size: 187778 relation: main_file file_date_updated: 2020-07-14T12:46:50Z has_accepted_license: '1' language: - iso: eng oa: 1 oa_version: None publisher: none pubrep_id: '254' status: public title: Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland type: report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5424' abstract: - lang: eng text: We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty. alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik - first_name: Raghav full_name: Gupta, Raghav last_name: Gupta - first_name: Ayush full_name: Kanodia, Ayush last_name: Kanodia citation: ama: Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria; 2014. doi:10.15479/AT:IST-2014-305-v1-1 apa: Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2014). Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. IST Austria. https://doi.org/10.15479/AT:IST-2014-305-v1-1 chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-305-v1-1. ieee: K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. IST Austria, 2014. ista: Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 12p. mla: Chatterjee, Krishnendu, et al. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014, doi:10.15479/AT:IST-2014-305-v1-1. short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014. date_created: 2018-12-12T11:39:15Z date_published: 2014-09-09T00:00:00Z date_updated: 2023-02-23T12:25:52Z day: '09' ddc: - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2014-305-v1-1 file: - access_level: open_access checksum: 35009d5fad01198341e6c1a3353481b7 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:51Z date_updated: 2020-07-14T12:46:51Z file_id: '5512' file_name: IST-2014-305-v1+1_main.pdf file_size: 655774 relation: main_file file_date_updated: 2020-07-14T12:46:51Z has_accepted_license: '1' language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: '12' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '305' related_material: record: - id: '1732' relation: later_version status: public - id: '5426' relation: later_version status: public status: public title: Qualitative analysis of POMDPs with temporal logic specifications for robotics applications type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5426' abstract: - lang: eng text: We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty. alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik - first_name: Raghav full_name: Gupta, Raghav last_name: Gupta - first_name: Ayush full_name: Kanodia, Ayush last_name: Kanodia citation: ama: Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria; 2014. doi:10.15479/AT:IST-2014-305-v2-1 apa: Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2014). Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. IST Austria. https://doi.org/10.15479/AT:IST-2014-305-v2-1 chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-305-v2-1. ieee: K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. IST Austria, 2014. ista: Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications, IST Austria, 10p. mla: Chatterjee, Krishnendu, et al. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IST Austria, 2014, doi:10.15479/AT:IST-2014-305-v2-1. short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria, 2014. date_created: 2018-12-12T11:39:16Z date_published: 2014-09-29T00:00:00Z date_updated: 2023-02-23T12:25:47Z day: '29' ddc: - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2014-305-v2-1 file: - access_level: open_access checksum: 730c0a8e97cf2712a884b2cc423f3919 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:15Z date_updated: 2020-07-14T12:46:51Z file_id: '5537' file_name: IST-2014-305-v2+1_main2.pdf file_size: 656019 relation: main_file file_date_updated: 2020-07-14T12:46:51Z has_accepted_license: '1' language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: '10' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '311' related_material: record: - id: '1732' relation: later_version status: public - id: '5424' relation: earlier_version status: public status: public title: Qualitative analysis of POMDPs with temporal logic specifications for robotics applications type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5423' abstract: - lang: eng text: 'We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. ' alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Alexander full_name: Kössler, Alexander last_name: Kössler - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 - first_name: Ulrich full_name: Schmid, Ulrich last_name: Schmid citation: ama: Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks. IST Austria; 2014. doi:10.15479/AT:IST-2014-300-v1-1 apa: Chatterjee, K., Kössler, A., Pavlogiannis, A., & Schmid, U. (2014). A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. IST Austria. https://doi.org/10.15479/AT:IST-2014-300-v1-1 chicago: Chatterjee, Krishnendu, Alexander Kössler, Andreas Pavlogiannis, and Ulrich Schmid. A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-300-v1-1. ieee: K. Chatterjee, A. Kössler, A. Pavlogiannis, and U. Schmid, A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. IST Austria, 2014. ista: Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. 2014. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks, IST Austria, 14p. mla: Chatterjee, Krishnendu, et al. A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks. IST Austria, 2014, doi:10.15479/AT:IST-2014-300-v1-1. short: K. Chatterjee, A. Kössler, A. Pavlogiannis, U. Schmid, A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks, IST Austria, 2014. date_created: 2018-12-12T11:39:15Z date_published: 2014-07-29T00:00:00Z date_updated: 2023-02-23T10:11:15Z day: '29' ddc: - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2014-300-v1-1 file: - access_level: open_access checksum: 4b8fde4d9ef6653837f6803921d83032 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:53Z date_updated: 2020-07-14T12:46:50Z file_id: '5514' file_name: IST-2014-300-v1+1_main.pdf file_size: 1270021 relation: main_file file_date_updated: 2020-07-14T12:46:50Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '14' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '300' related_material: record: - id: '1714' relation: later_version status: public status: public title: A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5427' abstract: - lang: eng text: 'We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.' alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: ama: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs. IST Austria; 2014. doi:10.15479/AT:IST-2014-314-v1-1 apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2014). Optimal tree-decomposition balancing and reachability on low treewidth graphs. IST Austria. https://doi.org/10.15479/AT:IST-2014-314-v1-1 chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-314-v1-1. ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Optimal tree-decomposition balancing and reachability on low treewidth graphs. IST Austria, 2014. ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Optimal tree-decomposition balancing and reachability on low treewidth graphs, IST Austria, 24p. mla: Chatterjee, Krishnendu, et al. Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs. IST Austria, 2014, doi:10.15479/AT:IST-2014-314-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs, IST Austria, 2014. date_created: 2018-12-12T11:39:16Z date_published: 2014-11-05T00:00:00Z date_updated: 2021-01-12T08:02:09Z day: '05' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2014-314-v1-1 file: - access_level: open_access checksum: 9d3b90bf4fff74664f182f2d95ef727a content_type: application/pdf creator: system date_created: 2018-12-12T11:53:10Z date_updated: 2020-07-14T12:46:52Z file_id: '5471' file_name: IST-2014-314-v1+1_long.pdf file_size: 405561 relation: main_file file_date_updated: 2020-07-14T12:46:52Z has_accepted_license: '1' language: - iso: eng month: '11' oa: 1 oa_version: Published Version page: '24' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '314' status: public title: Optimal tree-decomposition balancing and reachability on low treewidth graphs type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '5425' abstract: - lang: eng text: ' We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.' alternative_title: - IST Austria Technical Report author: - first_name: '1' full_name: Anonymous, 1 last_name: Anonymous - first_name: '2' full_name: Anonymous, 2 last_name: Anonymous - first_name: '3' full_name: Anonymous, 3 last_name: Anonymous - first_name: '4' full_name: Anonymous, 4 last_name: Anonymous citation: ama: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Optimal Cost Almost-Sure Reachability in POMDPs. IST Austria; 2014. apa: Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2014). Optimal cost almost-sure reachability in POMDPs. IST Austria. chicago: Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Optimal Cost Almost-Sure Reachability in POMDPs. IST Austria, 2014. ieee: 1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Optimal cost almost-sure reachability in POMDPs. IST Austria, 2014. ista: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2014. Optimal cost almost-sure reachability in POMDPs, IST Austria, 22p. mla: Anonymous, 1, et al. Optimal Cost Almost-Sure Reachability in POMDPs. IST Austria, 2014. short: 1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Optimal Cost Almost-Sure Reachability in POMDPs, IST Austria, 2014. date_created: 2018-12-12T11:39:15Z date_published: 2014-09-09T00:00:00Z date_updated: 2023-02-23T10:02:57Z day: '09' ddc: - '000' file: - access_level: open_access checksum: b9668a70d53c550b3cd64f0c77451c3d content_type: application/pdf creator: system date_created: 2018-12-12T11:53:17Z date_updated: 2020-07-14T12:46:51Z file_id: '5478' file_name: IST-2014-307-v1+1_main.pdf file_size: 2725429 relation: main_file - access_level: closed checksum: 808ada1dddecc48ca041526fcc6a9efd content_type: text/plain creator: dernst date_created: 2019-04-16T14:16:12Z date_updated: 2020-07-14T12:46:51Z file_id: '6322' file_name: IST-2014-307-v1+2_authors.txt file_size: 117 relation: main_file file_date_updated: 2020-07-14T12:46:51Z has_accepted_license: '1' language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: '22' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '307' related_material: record: - id: '1529' relation: later_version status: public scopus_import: 1 status: public title: Optimal cost almost-sure reachability in POMDPs type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ...