[{"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"publication":"International Conference on Computer Aided Verification","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"scopus_import":"1","ec_funded":1,"article_processing_charge":"Yes (in subscription journal)","author":[{"full_name":"Akshay, S.","first_name":"S.","last_name":"Akshay"},{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Meggendorfer","first_name":"Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165","full_name":"Meggendorfer, Tobias"},{"first_name":"Dorde","last_name":"Zikelic","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","full_name":"Zikelic, Dorde"}],"day":"17","file":[{"creator":"dernst","file_size":531745,"content_type":"application/pdf","relation":"main_file","file_name":"2023_LNCS_Akshay.pdf","success":1,"access_level":"open_access","date_created":"2023-09-20T08:46:43Z","checksum":"f143c8eedf609f20f2aad2eeb496d53f","file_id":"14349","date_updated":"2023-09-20T08:46:43Z"}],"title":"MDPs as distribution transformers: Affine invariant synthesis for safety objectives","project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"conference":{"location":"Paris, France","name":"CAV: Computer Aided Verification","start_date":"2023-07-17","end_date":"2023-07-22"},"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031377082"],"issn":["0302-9743"]},"doi":"10.1007/978-3-031-37709-9_5","quality_controlled":"1","acknowledgement":"This work was supported in part by the ERC CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385 as well as DST/CEFIPRA/INRIA project EQuaVE and SERB Matrices grant MTR/2018/00074.","year":"2023","_id":"14317","page":"86-112","type":"conference","oa_version":"Published Version","month":"07","abstract":[{"lang":"eng","text":"Markov decision processes can be viewed as transformers of probability distributions. While this view is useful from a practical standpoint to reason about trajectories of distributions, basic reachability and safety problems are known to be computationally intractable (i.e., Skolem-hard) to solve in such models. Further, we show that even for simple examples of MDPs, strategies for safety objectives over distributions can require infinite memory and randomization.\r\nIn light of this, we present a novel overapproximation approach to synthesize strategies in an MDP, such that a safety objective over the distributions is met. More precisely, we develop a new framework for template-based synthesis of certificates as affine distributional and inductive invariants for safety objectives in MDPs. We provide two algorithms within this framework. One can only synthesize memoryless strategies, but has relative completeness guarantees, while the other can synthesize general strategies. The runtime complexity of both algorithms is in PSPACE. We implement these algorithms and show that they can solve several non-trivial examples."}],"date_updated":"2025-07-14T09:09:56Z","volume":13966,"file_date_updated":"2023-09-20T08:46:43Z","date_created":"2023-09-10T22:01:12Z","alternative_title":["LNCS"],"status":"public","intvolume":"     13966","citation":{"ieee":"S. Akshay, K. Chatterjee, T. Meggendorfer, and D. Zikelic, “MDPs as distribution transformers: Affine invariant synthesis for safety objectives,” in <i>International Conference on Computer Aided Verification</i>, Paris, France, 2023, vol. 13966, pp. 86–112.","chicago":"Akshay, S., Krishnendu Chatterjee, Tobias Meggendorfer, and Dorde Zikelic. “MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives.” In <i>International Conference on Computer Aided Verification</i>, 13966:86–112. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-37709-9_5\">https://doi.org/10.1007/978-3-031-37709-9_5</a>.","short":"S. Akshay, K. Chatterjee, T. Meggendorfer, D. Zikelic, in:, International Conference on Computer Aided Verification, Springer Nature, 2023, pp. 86–112.","ama":"Akshay S, Chatterjee K, Meggendorfer T, Zikelic D. MDPs as distribution transformers: Affine invariant synthesis for safety objectives. In: <i>International Conference on Computer Aided Verification</i>. Vol 13966. Springer Nature; 2023:86-112. doi:<a href=\"https://doi.org/10.1007/978-3-031-37709-9_5\">10.1007/978-3-031-37709-9_5</a>","ista":"Akshay S, Chatterjee K, Meggendorfer T, Zikelic D. 2023. MDPs as distribution transformers: Affine invariant synthesis for safety objectives. International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13966, 86–112.","mla":"Akshay, S., et al. “MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives.” <i>International Conference on Computer Aided Verification</i>, vol. 13966, Springer Nature, 2023, pp. 86–112, doi:<a href=\"https://doi.org/10.1007/978-3-031-37709-9_5\">10.1007/978-3-031-37709-9_5</a>.","apa":"Akshay, S., Chatterjee, K., Meggendorfer, T., &#38; Zikelic, D. (2023). MDPs as distribution transformers: Affine invariant synthesis for safety objectives. In <i>International Conference on Computer Aided Verification</i> (Vol. 13966, pp. 86–112). Paris, France: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-37709-9_5\">https://doi.org/10.1007/978-3-031-37709-9_5</a>"},"publication_status":"published","oa":1,"has_accepted_license":"1","ddc":["000"],"date_published":"2023-07-17T00:00:00Z"},{"language":[{"iso":"eng"}],"conference":{"location":"Bordeaux, France","name":"MFCS: Symposium on Mathematical Foundations of Computer Science","start_date":"2023-08-28","end_date":"2023-09-01"},"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"quality_controlled":"1","doi":"10.4230/LIPIcs.MFCS.2023.15","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959772921"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"scopus_import":"1","article_processing_charge":"Yes","ec_funded":1,"publication":"48th International Symposium on Mathematical Foundations of Computer Science","department":[{"_id":"KrCh"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_number":"15","arxiv":1,"title":"Entropic risk for turn-based stochastic games","file":[{"date_created":"2023-10-09T09:19:11Z","access_level":"open_access","file_id":"14418","date_updated":"2023-10-09T09:19:11Z","checksum":"402281b17ed669bbf149d0fdf68ac201","file_size":826843,"content_type":"application/pdf","relation":"main_file","creator":"dernst","file_name":"2023_LIPIcsMFCS_Baier.pdf","success":1}],"day":"21","author":[{"full_name":"Baier, Christel","last_name":"Baier","first_name":"Christel"},{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","full_name":"Meggendorfer, Tobias","last_name":"Meggendorfer","first_name":"Tobias"},{"last_name":"Piribauer","first_name":"Jakob","full_name":"Piribauer, Jakob"}],"citation":{"mla":"Baier, Christel, et al. “Entropic Risk for Turn-Based Stochastic Games.” <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 272, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">10.4230/LIPIcs.MFCS.2023.15</a>.","ista":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2023. Entropic risk for turn-based stochastic games. 48th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 272, 15.","apa":"Baier, C., Chatterjee, K., Meggendorfer, T., &#38; Piribauer, J. (2023). Entropic risk for turn-based stochastic games. In <i>48th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 272). Bordeaux, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>","ama":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based stochastic games. In: <i>48th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">10.4230/LIPIcs.MFCS.2023.15</a>","short":"C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 48th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk for turn-based stochastic games,” in <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, Bordeaux, France, 2023, vol. 272.","chicago":"Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” In <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>."},"intvolume":"       272","external_id":{"arxiv":["2307.06611"]},"status":"public","alternative_title":["LIPIcs"],"date_published":"2023-08-21T00:00:00Z","ddc":["000"],"has_accepted_license":"1","oa":1,"publication_status":"published","_id":"14417","year":"2023","acknowledgement":"This work was partly funded by the ERC CoG 863818 (ForM-SMArt), the DFG Grant\r\n389792660 as part of TRR 248 (Foundations of Perspicuous Software Systems), the Cluster of\r\nExcellence EXC 2050/1 (CeTI, project ID 390696704, as part of Germany’s Excellence Strategy), and the DFG projects BA-1679/11-1 and BA-1679/12-1.","date_created":"2023-10-09T09:21:05Z","file_date_updated":"2023-10-09T09:19:11Z","volume":272,"oa_version":"Published Version","month":"08","type":"conference","abstract":[{"lang":"eng","text":"Entropic risk (ERisk) is an established risk measure in finance, quantifying risk by an exponential re-weighting of rewards. We study ERisk for the first time in the context of turn-based stochastic games with the total reward objective. This gives rise to an objective function that demands the control of systems in a risk-averse manner. We show that the resulting games are determined and, in particular, admit optimal memoryless deterministic strategies. This contrasts risk measures that previously have been considered in the special case of Markov decision processes and that require randomization and/or memory. We provide several results on the decidability and the computational complexity of the threshold problem, i.e. whether the optimal value of ERisk exceeds a given threshold. In the most general case, the problem is decidable subject to Shanuel’s conjecture. If all inputs are rational, the resulting threshold problem can be solved using algebraic numbers, leading to decidability via a polynomial-time reduction to the existential theory of the reals. Further restrictions on the encoding of the input allow the solution of the threshold problem in NP∩coNP. Finally, an approximation algorithm for the optimal value of ERisk is provided."}],"date_updated":"2025-07-14T09:09:57Z"},{"_id":"14518","year":"2023","acknowledgement":"This research was supported in part by ISF grant no. 1679/21, ERC CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie Grant Agreement No. 665385.","date_created":"2023-11-12T23:00:56Z","file_date_updated":"2023-11-13T10:16:10Z","volume":372,"date_updated":"2025-07-14T09:09:57Z","abstract":[{"lang":"eng","text":"We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets."}],"oa_version":"Published Version","month":"09","type":"conference","page":"141-148","citation":{"chicago":"Avni, Guy, Tobias Meggendorfer, Suman Sadhukhan, Josef Tkadlec, and Dorde Zikelic. “Reachability Poorman Discrete-Bidding Games.” In <i>Frontiers in Artificial Intelligence and Applications</i>, 372:141–48. IOS Press, 2023. <a href=\"https://doi.org/10.3233/FAIA230264\">https://doi.org/10.3233/FAIA230264</a>.","ieee":"G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, and D. Zikelic, “Reachability poorman discrete-bidding games,” in <i>Frontiers in Artificial Intelligence and Applications</i>, Krakow, Poland, 2023, vol. 372, pp. 141–148.","short":"G. Avni, T. Meggendorfer, S. Sadhukhan, J. Tkadlec, D. Zikelic, in:, Frontiers in Artificial Intelligence and Applications, IOS Press, 2023, pp. 141–148.","ama":"Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. Reachability poorman discrete-bidding games. In: <i>Frontiers in Artificial Intelligence and Applications</i>. Vol 372. IOS Press; 2023:141-148. doi:<a href=\"https://doi.org/10.3233/FAIA230264\">10.3233/FAIA230264</a>","apa":"Avni, G., Meggendorfer, T., Sadhukhan, S., Tkadlec, J., &#38; Zikelic, D. (2023). Reachability poorman discrete-bidding games. In <i>Frontiers in Artificial Intelligence and Applications</i> (Vol. 372, pp. 141–148). Krakow, Poland: IOS Press. <a href=\"https://doi.org/10.3233/FAIA230264\">https://doi.org/10.3233/FAIA230264</a>","ista":"Avni G, Meggendorfer T, Sadhukhan S, Tkadlec J, Zikelic D. 2023. Reachability poorman discrete-bidding games. Frontiers in Artificial Intelligence and Applications. ECAI: European Conference on Artificial Intelligence vol. 372, 141–148.","mla":"Avni, Guy, et al. “Reachability Poorman Discrete-Bidding Games.” <i>Frontiers in Artificial Intelligence and Applications</i>, vol. 372, IOS Press, 2023, pp. 141–48, doi:<a href=\"https://doi.org/10.3233/FAIA230264\">10.3233/FAIA230264</a>."},"intvolume":"       372","status":"public","external_id":{"arxiv":["2307.15218"]},"ddc":["000"],"date_published":"2023-09-28T00:00:00Z","has_accepted_license":"1","publication_status":"published","oa":1,"scopus_import":"1","ec_funded":1,"article_processing_charge":"No","tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)","image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"publication":"Frontiers in Artificial Intelligence and Applications","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publisher":"IOS Press","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Reachability poorman discrete-bidding games","arxiv":1,"file":[{"checksum":"1390ca38480fa4cf286b0f1a42e8c12f","file_id":"14529","date_updated":"2023-11-13T10:16:10Z","access_level":"open_access","date_created":"2023-11-13T10:16:10Z","file_name":"2023_FAIA_Avni.pdf","success":1,"creator":"dernst","file_size":501011,"relation":"main_file","content_type":"application/pdf"}],"day":"28","author":[{"full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy","last_name":"Avni"},{"full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","last_name":"Meggendorfer"},{"full_name":"Sadhukhan, Suman","last_name":"Sadhukhan","first_name":"Suman"},{"full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","first_name":"Josef"},{"orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","full_name":"Zikelic, Dorde","first_name":"Dorde","last_name":"Zikelic"}],"language":[{"iso":"eng"}],"conference":{"end_date":"2023-10-04","location":"Krakow, Poland","name":"ECAI: European Conference on Artificial Intelligence","start_date":"2023-09-30"},"project":[{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"665385"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"quality_controlled":"1","doi":"10.3233/FAIA230264","publication_identifier":{"issn":["0922-6389"],"isbn":["9781643684369"]}},{"publisher":"Zenodo","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","department":[{"_id":"KrCh"}],"_id":"14990","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"No","author":[{"first_name":"Tobias","last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1"}],"month":"01","type":"research_data_reference","oa_version":"Published Version","date_updated":"2024-02-27T07:19:32Z","day":"18","abstract":[{"lang":"eng","text":"The software artefact to evaluate the approximation of stationary distributions implementation."}],"title":"Artefact for: Correct Approximation of Stationary Distributions","date_created":"2024-02-14T14:27:06Z","status":"public","related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"13139"}]},"citation":{"ista":"Meggendorfer T. 2023. Artefact for: Correct Approximation of Stationary Distributions, Zenodo, <a href=\"https://doi.org/10.5281/ZENODO.7548214\">10.5281/ZENODO.7548214</a>.","mla":"Meggendorfer, Tobias. <i>Artefact for: Correct Approximation of Stationary Distributions</i>. Zenodo, 2023, doi:<a href=\"https://doi.org/10.5281/ZENODO.7548214\">10.5281/ZENODO.7548214</a>.","apa":"Meggendorfer, T. (2023). Artefact for: Correct Approximation of Stationary Distributions. Zenodo. <a href=\"https://doi.org/10.5281/ZENODO.7548214\">https://doi.org/10.5281/ZENODO.7548214</a>","ama":"Meggendorfer T. Artefact for: Correct Approximation of Stationary Distributions. 2023. doi:<a href=\"https://doi.org/10.5281/ZENODO.7548214\">10.5281/ZENODO.7548214</a>","short":"T. Meggendorfer, (2023).","ieee":"T. Meggendorfer, “Artefact for: Correct Approximation of Stationary Distributions.” Zenodo, 2023.","chicago":"Meggendorfer, Tobias. “Artefact for: Correct Approximation of Stationary Distributions.” Zenodo, 2023. <a href=\"https://doi.org/10.5281/ZENODO.7548214\">https://doi.org/10.5281/ZENODO.7548214</a>."},"oa":1,"has_accepted_license":"1","doi":"10.5281/ZENODO.7548214","ddc":["000"],"date_published":"2023-01-18T00:00:00Z","main_file_link":[{"url":"https://doi.org/10.5281/zenodo.7548214","open_access":"1"}]},{"citation":{"short":"T. Meggendorfer, in:, TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2023, pp. 489–507.","ieee":"T. Meggendorfer, “Correct approximation of stationary distributions,” in <i>TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems</i>, Paris, France, 2023, vol. 13993, pp. 489–507.","chicago":"Meggendorfer, Tobias. “Correct Approximation of Stationary Distributions.” In <i>TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems</i>, 13993:489–507. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-30823-9_25\">https://doi.org/10.1007/978-3-031-30823-9_25</a>.","mla":"Meggendorfer, Tobias. “Correct Approximation of Stationary Distributions.” <i>TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 13993, Springer Nature, 2023, pp. 489–507, doi:<a href=\"https://doi.org/10.1007/978-3-031-30823-9_25\">10.1007/978-3-031-30823-9_25</a>.","ista":"Meggendorfer T. 2023. Correct approximation of stationary distributions. TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 13993, 489–507.","apa":"Meggendorfer, T. (2023). Correct approximation of stationary distributions. In <i>TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 13993, pp. 489–507). Paris, France: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-30823-9_25\">https://doi.org/10.1007/978-3-031-30823-9_25</a>","ama":"Meggendorfer T. Correct approximation of stationary distributions. In: <i>TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 13993. Springer Nature; 2023:489-507. doi:<a href=\"https://doi.org/10.1007/978-3-031-30823-9_25\">10.1007/978-3-031-30823-9_25</a>"},"intvolume":"     13993","related_material":{"record":[{"id":"14990","status":"public","relation":"research_data"}]},"external_id":{"arxiv":["2301.08137"]},"status":"public","alternative_title":["LNCS"],"date_published":"2023-04-22T00:00:00Z","ddc":["000"],"has_accepted_license":"1","oa":1,"publication_status":"published","_id":"13139","year":"2023","file_date_updated":"2023-06-19T07:18:40Z","date_created":"2023-06-18T22:00:46Z","volume":13993,"date_updated":"2024-02-27T07:19:33Z","abstract":[{"lang":"eng","text":"A classical problem for Markov chains is determining their stationary (or steady-state) distribution. This problem has an equally classical solution based on eigenvectors and linear equation systems. However, this approach does not scale to large instances, and iterative solutions are desirable. It turns out that a naive approach, as used by current model checkers, may yield completely wrong results. We present a new approach, which utilizes recent advances in partial exploration and mean payoff computation to obtain a correct, converging approximation."}],"type":"conference","month":"04","oa_version":"Published Version","page":"489-507","language":[{"iso":"eng"}],"conference":{"start_date":"2023-04-22","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","location":"Paris, France","end_date":"2023-04-27"},"quality_controlled":"1","doi":"10.1007/978-3-031-30823-9_25","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031308222"],"issn":["0302-9743"]},"scopus_import":"1","article_processing_charge":"No","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication":"TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems","department":[{"_id":"KrCh"}],"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Correct approximation of stationary distributions","arxiv":1,"file":[{"date_created":"2023-06-19T07:18:40Z","access_level":"open_access","date_updated":"2023-06-19T07:18:40Z","file_id":"13148","checksum":"59f707a3949c03793251b0d04c62542a","content_type":"application/pdf","relation":"main_file","file_size":521951,"creator":"dernst","success":1,"file_name":"2023_LNCS_Meggendorfer.pdf"}],"day":"22","author":[{"last_name":"Meggendorfer","first_name":"Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","full_name":"Meggendorfer, Tobias"}]},{"scopus_import":"1","article_processing_charge":"No","publication":"38th Annual ACM/IEEE Symposium on Logic in Computer Science","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Institute of Electrical and Electronics Engineers","arxiv":1,"title":"Stopping criteria for value iteration on stochastic games with quantitative objectives","day":"01","author":[{"full_name":"Kretinsky, Jan","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","first_name":"Jan"},{"orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","full_name":"Meggendorfer, Tobias","first_name":"Tobias","last_name":"Meggendorfer"},{"last_name":"Weininger","first_name":"Maximilian","id":"02ab0197-cc70-11ed-ab61-918e71f56881","full_name":"Weininger, Maximilian"}],"language":[{"iso":"eng"}],"isi":1,"conference":{"end_date":"2023-06-29","location":"Boston, MA, United States","name":"LICS: Symposium on Logic in Computer Science","start_date":"2023-06-26"},"quality_controlled":"1","doi":"10.1109/LICS56636.2023.10175771","publication_identifier":{"issn":["1043-6871"],"isbn":["9798350335873"]},"_id":"13967","year":"2023","acknowledgement":"This research was funded in part by DFG projects 383882557 “SUV” and 427755713 “GOPro”.","date_created":"2023-08-06T22:01:10Z","volume":2023,"date_updated":"2023-12-13T12:06:10Z","abstract":[{"text":"A classic solution technique for Markov decision processes (MDP) and stochastic games (SG) is value iteration (VI). Due to its good practical performance, this approximative approach is typically preferred over exact techniques, even though no practical bounds on the imprecision of the result could be given until recently. As a consequence, even the most used model checkers could return arbitrarily wrong results. Over the past decade, different works derived stopping criteria, indicating when the precision reaches the desired level, for various settings, in particular MDP with reachability, total reward, and mean payoff, and SG with reachability.In this paper, we provide the first stopping criteria for VI on SG with total reward and mean payoff, yielding the first anytime algorithms in these settings. To this end, we provide the solution in two flavours: First through a reduction to the MDP case and second directly on SG. The former is simpler and automatically utilizes any advances on MDP. The latter allows for more local computations, heading towards better practical efficiency.Our solution unifies the previously mentioned approaches for MDP and SG and their underlying ideas. To achieve this, we isolate objective-specific subroutines as well as identify objective-independent concepts. These structural concepts, while surprisingly simple, form the very essence of the unified solution.","lang":"eng"}],"month":"07","oa_version":"Preprint","type":"conference","citation":{"short":"J. Kretinsky, T. Meggendorfer, M. Weininger, in:, 38th Annual ACM/IEEE Symposium on Logic in Computer Science, Institute of Electrical and Electronics Engineers, 2023.","chicago":"Kretinsky, Jan, Tobias Meggendorfer, and Maximilian Weininger. “Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives.” In <i>38th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Vol. 2023. Institute of Electrical and Electronics Engineers, 2023. <a href=\"https://doi.org/10.1109/LICS56636.2023.10175771\">https://doi.org/10.1109/LICS56636.2023.10175771</a>.","ieee":"J. Kretinsky, T. Meggendorfer, and M. Weininger, “Stopping criteria for value iteration on stochastic games with quantitative objectives,” in <i>38th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Boston, MA, United States, 2023, vol. 2023.","apa":"Kretinsky, J., Meggendorfer, T., &#38; Weininger, M. (2023). Stopping criteria for value iteration on stochastic games with quantitative objectives. In <i>38th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (Vol. 2023). Boston, MA, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/LICS56636.2023.10175771\">https://doi.org/10.1109/LICS56636.2023.10175771</a>","ista":"Kretinsky J, Meggendorfer T, Weininger M. 2023. Stopping criteria for value iteration on stochastic games with quantitative objectives. 38th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Symposium on Logic in Computer Science vol. 2023.","mla":"Kretinsky, Jan, et al. “Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives.” <i>38th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, vol. 2023, Institute of Electrical and Electronics Engineers, 2023, doi:<a href=\"https://doi.org/10.1109/LICS56636.2023.10175771\">10.1109/LICS56636.2023.10175771</a>.","ama":"Kretinsky J, Meggendorfer T, Weininger M. Stopping criteria for value iteration on stochastic games with quantitative objectives. In: <i>38th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Vol 2023. Institute of Electrical and Electronics Engineers; 2023. doi:<a href=\"https://doi.org/10.1109/LICS56636.2023.10175771\">10.1109/LICS56636.2023.10175771</a>"},"intvolume":"      2023","external_id":{"arxiv":["2304.09930"],"isi":["001036707700042"]},"status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2304.09930","open_access":"1"}],"date_published":"2023-07-01T00:00:00Z","publication_status":"published","oa":1},{"language":[{"iso":"eng"}],"conference":{"end_date":"2023-07-22","start_date":"2023-07-17","name":"CAV: Computer Aided Verification","location":"Paris, France"},"publication_identifier":{"isbn":["9783031377051"],"eissn":["1611-3349"],"issn":["0302-9743"]},"quality_controlled":"1","doi":"10.1007/978-3-031-37706-8_20","department":[{"_id":"KrCh"}],"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","article_processing_charge":"Yes (in subscription journal)","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication":"35th International Conference on Computer Aided Verification ","file":[{"success":1,"file_name":"2023_LNCS_CAV_Kretinsky.pdf","content_type":"application/pdf","relation":"main_file","file_size":428354,"creator":"dernst","date_updated":"2023-09-06T08:25:50Z","file_id":"14276","checksum":"ed66278b61bb869e1baba3d9b9081271","date_created":"2023-09-06T08:25:50Z","access_level":"open_access"}],"day":"17","author":[{"last_name":"Kretinsky","first_name":"Jan","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"},{"full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer","first_name":"Tobias"},{"last_name":"Prokop","first_name":"Maximilian","full_name":"Prokop, Maximilian"},{"first_name":"Sabine","last_name":"Rieder","full_name":"Rieder, Sabine"}],"title":"Guessing winning policies in LTL synthesis by semantic learning","status":"public","alternative_title":["LNCS"],"citation":{"ama":"Kretinsky J, Meggendorfer T, Prokop M, Rieder S. Guessing winning policies in LTL synthesis by semantic learning. In: <i>35th International Conference on Computer Aided Verification </i>. Vol 13964. Springer Nature; 2023:390-414. doi:<a href=\"https://doi.org/10.1007/978-3-031-37706-8_20\">10.1007/978-3-031-37706-8_20</a>","apa":"Kretinsky, J., Meggendorfer, T., Prokop, M., &#38; Rieder, S. (2023). Guessing winning policies in LTL synthesis by semantic learning. In <i>35th International Conference on Computer Aided Verification </i> (Vol. 13964, pp. 390–414). Paris, France: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-37706-8_20\">https://doi.org/10.1007/978-3-031-37706-8_20</a>","ista":"Kretinsky J, Meggendorfer T, Prokop M, Rieder S. 2023. Guessing winning policies in LTL synthesis by semantic learning. 35th International Conference on Computer Aided Verification . CAV: Computer Aided Verification, LNCS, vol. 13964, 390–414.","mla":"Kretinsky, Jan, et al. “Guessing Winning Policies in LTL Synthesis by Semantic Learning.” <i>35th International Conference on Computer Aided Verification </i>, vol. 13964, Springer Nature, 2023, pp. 390–414, doi:<a href=\"https://doi.org/10.1007/978-3-031-37706-8_20\">10.1007/978-3-031-37706-8_20</a>.","chicago":"Kretinsky, Jan, Tobias Meggendorfer, Maximilian Prokop, and Sabine Rieder. “Guessing Winning Policies in LTL Synthesis by Semantic Learning.” In <i>35th International Conference on Computer Aided Verification </i>, 13964:390–414. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-37706-8_20\">https://doi.org/10.1007/978-3-031-37706-8_20</a>.","ieee":"J. Kretinsky, T. Meggendorfer, M. Prokop, and S. Rieder, “Guessing winning policies in LTL synthesis by semantic learning,” in <i>35th International Conference on Computer Aided Verification </i>, Paris, France, 2023, vol. 13964, pp. 390–414.","short":"J. Kretinsky, T. Meggendorfer, M. Prokop, S. Rieder, in:, 35th International Conference on Computer Aided Verification , Springer Nature, 2023, pp. 390–414."},"intvolume":"     13964","has_accepted_license":"1","oa":1,"publication_status":"published","ddc":["000"],"date_published":"2023-07-17T00:00:00Z","year":"2023","acknowledgement":"This research was funded in part by the German Research Foundation (DFG) project 427755713 Group-By Objectives in Probabilistic Verification (GOPro).","_id":"14259","date_updated":"2023-09-06T08:27:33Z","abstract":[{"lang":"eng","text":"We provide a learning-based technique for guessing a winning strategy in a parity game originating from an LTL synthesis problem. A cheaply obtained guess can be useful in several applications. Not only can the guessed strategy be applied as best-effort in cases where the game’s huge size prohibits rigorous approaches, but it can also increase the scalability of rigorous LTL synthesis in several ways. Firstly, checking whether a guessed strategy is winning is easier than constructing one. Secondly, even if the guess is wrong in some places, it can be fixed by strategy iteration faster than constructing one from scratch. Thirdly, the guess can be used in on-the-fly approaches to prioritize exploration in the most fruitful directions.\r\nIn contrast to previous works, we (i) reflect the highly structured logical information in game’s states, the so-called semantic labelling, coming from the recent LTL-to-automata translations, and (ii) learn to reflect it properly by learning from previously solved games, bringing the solving process closer to human-like reasoning."}],"month":"07","type":"conference","oa_version":"Published Version","page":"390-414","date_created":"2023-09-03T22:01:16Z","file_date_updated":"2023-09-06T08:25:50Z","volume":13964},{"publication":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","article_processing_charge":"No","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"title":"Faster algorithm for turn-based stochastic games with bounded treewidth","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Meggendorfer","first_name":"Tobias","full_name":"Meggendorfer, Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165"},{"full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","last_name":"Saona Urmeneta"},{"full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","last_name":"Svoboda","first_name":"Jakub"}],"day":"01","conference":{"start_date":"2023-01-22","name":"SODA: Symposium on Discrete Algorithms","location":"Florence, Italy","end_date":"2023-01-25"},"language":[{"iso":"eng"}],"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"doi":"10.1137/1.9781611977554.ch173","quality_controlled":"1","publication_identifier":{"isbn":["9781611977554"]},"_id":"12676","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","year":"2023","date_created":"2023-02-24T12:20:47Z","page":"4590-4605","month":"02","type":"conference","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth."}],"date_updated":"2025-07-14T09:09:50Z","citation":{"short":"K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 4590–4605.","chicago":"Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 4590–4605. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>.","ieee":"K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster algorithm for turn-based stochastic games with bounded treewidth,” in <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy, 2023, pp. 4590–4605.","apa":"Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., &#38; Svoboda, J. (2023). Faster algorithm for turn-based stochastic games with bounded treewidth. In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>","ista":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster algorithm for turn-based stochastic games with bounded treewidth. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 4590–4605.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2023, pp. 4590–605, doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>.","ama":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm for turn-based stochastic games with bounded treewidth. In: <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2023:4590-4605. doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>"},"status":"public","date_published":"2023-02-01T00:00:00Z","main_file_link":[{"url":"https://doi.org/10.1137/1.9781611977554.ch173","open_access":"1"}],"oa":1,"publication_status":"published"},{"_id":"10602","year":"2022","acknowledgement":"This work is partially funded by the German Research Foundation (DFG) projects Verified Model Checkers (No. 317422601) and Statistical Unbounded Verification (No. 383882557), and the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research. It is an extended version of [21], including all proofs together with further explanations and examples. Moreover, we provide a new, more efficient construction based on (total) preorders, unifying previous optimizations. Experiments are performed with a new, performant implementation, comparing our approach to the current state of the art.","file_date_updated":"2022-01-07T07:50:31Z","date_created":"2022-01-06T12:37:27Z","volume":59,"type":"journal_article","month":"10","oa_version":"Published Version","date_updated":"2023-08-02T13:49:28Z","abstract":[{"lang":"eng","text":"Transforming ω-automata into parity automata is traditionally done using appearance records. We present an efficient variant of this idea, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and show that our method produces significantly smaller automata than previous approaches."}],"page":"585-618","citation":{"ama":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. Index appearance record with preorders. <i>Acta Informatica</i>. 2022;59:585-618. doi:<a href=\"https://doi.org/10.1007/s00236-021-00412-y\">10.1007/s00236-021-00412-y</a>","ista":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2022. Index appearance record with preorders. Acta Informatica. 59, 585–618.","mla":"Kretinsky, Jan, et al. “Index Appearance Record with Preorders.” <i>Acta Informatica</i>, vol. 59, Springer Nature, 2022, pp. 585–618, doi:<a href=\"https://doi.org/10.1007/s00236-021-00412-y\">10.1007/s00236-021-00412-y</a>.","apa":"Kretinsky, J., Meggendorfer, T., Waldmann, C., &#38; Weininger, M. (2022). Index appearance record with preorders. <i>Acta Informatica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00236-021-00412-y\">https://doi.org/10.1007/s00236-021-00412-y</a>","ieee":"J. Kretinsky, T. Meggendorfer, C. Waldmann, and M. Weininger, “Index appearance record with preorders,” <i>Acta Informatica</i>, vol. 59. Springer Nature, pp. 585–618, 2022.","chicago":"Kretinsky, Jan, Tobias Meggendorfer, Clara Waldmann, and Maximilian Weininger. “Index Appearance Record with Preorders.” <i>Acta Informatica</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00236-021-00412-y\">https://doi.org/10.1007/s00236-021-00412-y</a>.","short":"J. Kretinsky, T. Meggendorfer, C. Waldmann, M. Weininger, Acta Informatica 59 (2022) 585–618."},"intvolume":"        59","external_id":{"isi":["000735765500001"]},"status":"public","date_published":"2022-10-01T00:00:00Z","ddc":["000"],"has_accepted_license":"1","publication_status":"published","oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","article_processing_charge":"Yes (via OA deal)","scopus_import":"1","publication":"Acta Informatica","department":[{"_id":"KrCh"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer Nature","title":"Index appearance record with preorders","file":[{"checksum":"bf1c195b6aaf59e8530cf9e3a9d731f7","date_updated":"2022-01-07T07:50:31Z","file_id":"10603","access_level":"open_access","date_created":"2022-01-07T07:50:31Z","success":1,"file_name":"2021_ActaInfor_Křetínský.pdf","creator":"cchlebak","content_type":"application/pdf","relation":"main_file","file_size":1066082}],"day":"01","author":[{"last_name":"Kretinsky","first_name":"Jan","full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881"},{"full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","last_name":"Meggendorfer"},{"full_name":"Waldmann, Clara","first_name":"Clara","last_name":"Waldmann"},{"full_name":"Weininger, Maximilian","last_name":"Weininger","first_name":"Maximilian"}],"language":[{"iso":"eng"}],"keyword":["computer networks and communications","information systems","software"],"isi":1,"project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"quality_controlled":"1","doi":"10.1007/s00236-021-00412-y","publication_identifier":{"eissn":["1432-0525"],"issn":["0001-5903"]}},{"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Amir Kafshdar","last_name":"Goharshady","full_name":"Goharshady, Amir Kafshdar","id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584"},{"full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer","first_name":"Tobias"},{"id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","last_name":"Zikelic","first_name":"Dorde"}],"file":[{"date_updated":"2022-08-29T09:17:01Z","file_id":"12003","checksum":"24e0f810ec52735a90ade95198bc641d","date_created":"2022-08-29T09:17:01Z","access_level":"open_access","success":1,"file_name":"2022_LNCS_Chatterjee.pdf","relation":"main_file","content_type":"application/pdf","file_size":505094,"creator":"alisjak"}],"day":"07","title":"Sound and complete certificates for auantitative termination analysis of probabilistic programs","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer","department":[{"_id":"KrCh"}],"publication":"Proceedings of the 34th International Conference on Computer Aided Verification","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ec_funded":1,"article_processing_charge":"Yes (in subscription journal)","scopus_import":"1","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031131844"],"issn":["0302-9743"]},"doi":"10.1007/978-3-031-13185-1_4","quality_controlled":"1","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"conference":{"start_date":"2022-08-07","location":"Haifa, Israel","name":"CAV: Computer Aided Verification","end_date":"2022-08-10"},"isi":1,"language":[{"iso":"eng"}],"page":"55-78","month":"08","oa_version":"Published Version","type":"conference","date_updated":"2025-07-14T09:09:58Z","abstract":[{"text":"We consider the quantitative problem of obtaining lower-bounds on the probability of termination of a given non-deterministic probabilistic program. Specifically, given a non-termination threshold p∈[0,1], we aim for certificates proving that the program terminates with probability at least 1−p. The basic idea of our approach is to find a terminating stochastic invariant, i.e. a subset SI of program states such that (i) the probability of the program ever leaving SI is no more than p, and (ii) almost-surely, the program either leaves SI or terminates.\r\n\r\nWhile stochastic invariants are already well-known, we provide the first proof that the idea above is not only sound, but also complete for quantitative termination analysis. We then introduce a novel sound and complete characterization of stochastic invariants that enables template-based approaches for easy synthesis of quantitative termination certificates, especially in affine or polynomial forms. Finally, by combining this idea with the existing martingale-based methods that are relatively complete for qualitative termination analysis, we obtain the first automated, sound, and relatively complete algorithm for quantitative termination analysis. Notably, our completeness guarantees for quantitative termination analysis are as strong as the best-known methods for the qualitative variant.\r\n\r\nOur prototype implementation demonstrates the effectiveness of our approach on various probabilistic programs. We also demonstrate that our algorithm certifies lower bounds on termination probability for probabilistic programs that are beyond the reach of previous methods.","lang":"eng"}],"volume":13371,"file_date_updated":"2022-08-29T09:17:01Z","date_created":"2022-08-28T22:02:02Z","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt), the HKUST-Kaisa Joint Research Institute Project Grant HKJRI3A-055, the HKUST Startup Grant R9272 and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385.","year":"2022","_id":"12000","publication_status":"published","oa":1,"has_accepted_license":"1","ddc":["000"],"date_published":"2022-08-07T00:00:00Z","alternative_title":["LNCS"],"external_id":{"isi":["000870304500004"]},"status":"public","intvolume":"     13371","related_material":{"record":[{"status":"public","id":"14539","relation":"dissertation_contains"}]},"citation":{"ama":"Chatterjee K, Goharshady AK, Meggendorfer T, Zikelic D. Sound and complete certificates for auantitative termination analysis of probabilistic programs. In: <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>. Vol 13371. Springer; 2022:55-78. doi:<a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">10.1007/978-3-031-13185-1_4</a>","mla":"Chatterjee, Krishnendu, et al. “Sound and Complete Certificates for Auantitative Termination Analysis of Probabilistic Programs.” <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>, vol. 13371, Springer, 2022, pp. 55–78, doi:<a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">10.1007/978-3-031-13185-1_4</a>.","ista":"Chatterjee K, Goharshady AK, Meggendorfer T, Zikelic D. 2022. Sound and complete certificates for auantitative termination analysis of probabilistic programs. Proceedings of the 34th International Conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 13371, 55–78.","apa":"Chatterjee, K., Goharshady, A. K., Meggendorfer, T., &#38; Zikelic, D. (2022). Sound and complete certificates for auantitative termination analysis of probabilistic programs. In <i>Proceedings of the 34th International Conference on Computer Aided Verification</i> (Vol. 13371, pp. 55–78). Haifa, Israel: Springer. <a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">https://doi.org/10.1007/978-3-031-13185-1_4</a>","ieee":"K. Chatterjee, A. K. Goharshady, T. Meggendorfer, and D. Zikelic, “Sound and complete certificates for auantitative termination analysis of probabilistic programs,” in <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>, Haifa, Israel, 2022, vol. 13371, pp. 55–78.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Tobias Meggendorfer, and Dorde Zikelic. “Sound and Complete Certificates for Auantitative Termination Analysis of Probabilistic Programs.” In <i>Proceedings of the 34th International Conference on Computer Aided Verification</i>, 13371:55–78. Springer, 2022. <a href=\"https://doi.org/10.1007/978-3-031-13185-1_4\">https://doi.org/10.1007/978-3-031-13185-1_4</a>.","short":"K. Chatterjee, A.K. Goharshady, T. Meggendorfer, D. Zikelic, in:, Proceedings of the 34th International Conference on Computer Aided Verification, Springer, 2022, pp. 55–78."}},{"date_published":"2022-12-14T00:00:00Z","ddc":["000"],"publication_status":"published","oa":1,"has_accepted_license":"1","intvolume":"       250","citation":{"mla":"Ahmadi, Ali, et al. “Algorithms and Hardness Results for Computing Cores of Markov Chains.” <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 250, 29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">10.4230/LIPIcs.FSTTCS.2022.29</a>.","ista":"Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic D. 2022. Algorithms and hardness results for computing cores of Markov chains. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTC: Foundations of Software Technology and Theoretical Computer Science vol. 250, 29.","apa":"Ahmadi, A., Chatterjee, K., Goharshady, A. K., Meggendorfer, T., Safavi Hemami, R., &#38; Zikelic, D. (2022). Algorithms and hardness results for computing cores of Markov chains. In <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 250). Madras, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>","ama":"Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic D. Algorithms and hardness results for computing cores of Markov chains. In: <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">10.4230/LIPIcs.FSTTCS.2022.29</a>","short":"A. Ahmadi, K. Chatterjee, A.K. Goharshady, T. Meggendorfer, R. Safavi Hemami, D. Zikelic, in:, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ieee":"A. Ahmadi, K. Chatterjee, A. K. Goharshady, T. Meggendorfer, R. Safavi Hemami, and D. Zikelic, “Algorithms and hardness results for computing cores of Markov chains,” in <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Madras, India, 2022, vol. 250.","chicago":"Ahmadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi Hemami, and Dorde Zikelic. “Algorithms and Hardness Results for Computing Cores of Markov Chains.” In <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>."},"status":"public","volume":250,"date_created":"2023-01-01T23:00:50Z","file_date_updated":"2023-01-20T10:39:44Z","oa_version":"Published Version","month":"12","type":"conference","abstract":[{"text":"Given a Markov chain M = (V, v_0, δ), with state space V and a starting state v_0, and a probability threshold ε, an ε-core is a subset C of states that is left with probability at most ε. More formally, C ⊆ V is an ε-core, iff ℙ[reach (V\\C)] ≤ ε. Cores have been applied in a wide variety of verification problems over Markov chains, Markov decision processes, and probabilistic programs, as a means of discarding uninteresting and low-probability parts of a probabilistic system and instead being able to focus on the states that are likely to be encountered in a real-world run. In this work, we focus on the problem of computing a minimal ε-core in a Markov chain. Our contributions include both negative and positive results: (i) We show that the decision problem on the existence of an ε-core of a given size is NP-complete. This solves an open problem posed in [Jan Kretínský and Tobias Meggendorfer, 2020]. We additionally show that the problem remains NP-complete even when limited to acyclic Markov chains with bounded maximal vertex degree; (ii) We provide a polynomial time algorithm for computing a minimal ε-core on Markov chains over control-flow graphs of structured programs. A straightforward combination of our algorithm with standard branch prediction techniques allows one to apply the idea of cores to find a subset of program lines that are left with low probability and then focus any desired static analysis on this core subset.","lang":"eng"}],"date_updated":"2025-07-14T09:09:55Z","_id":"12102","acknowledgement":"The research was partially supported by the Hong Kong Research Grants Council ECS\r\nProject No. 26208122, ERC CoG 863818 (FoRM-SMArt), the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385, HKUST– Kaisa Joint Research Institute Project Grant HKJRI3A-055 and HKUST Startup Grant R9272. Ali Ahmadi and Roodabeh Safavi were interns at HKUST.","year":"2022","doi":"10.4230/LIPIcs.FSTTCS.2022.29","quality_controlled":"1","publication_identifier":{"isbn":["9783959772617"],"issn":["1868-8969"]},"conference":{"name":"FSTTC: Foundations of Software Technology and Theoretical Computer Science","location":"Madras, India","start_date":"2022-12-18","end_date":"2022-12-20"},"language":[{"iso":"eng"}],"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"},{"grant_number":"665385","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program"}],"article_number":"29","title":"Algorithms and hardness results for computing cores of Markov chains","author":[{"full_name":"Ahmadi, Ali","last_name":"Ahmadi","first_name":"Ali"},{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0003-1702-6584","id":"391365CE-F248-11E8-B48F-1D18A9856A87","full_name":"Goharshady, Amir Kafshdar","last_name":"Goharshady","first_name":"Amir Kafshdar"},{"full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","last_name":"Meggendorfer"},{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh","last_name":"Safavi Hemami"},{"first_name":"Dorde","last_name":"Zikelic","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","full_name":"Zikelic, Dorde"}],"file":[{"access_level":"open_access","date_created":"2023-01-20T10:39:44Z","checksum":"6660c802489013f034c9e8bd57f4d46e","file_id":"12324","date_updated":"2023-01-20T10:39:44Z","creator":"dernst","file_size":872534,"relation":"main_file","content_type":"application/pdf","file_name":"2022_LIPICs_Ahmadi.pdf","success":1}],"day":"14","publication":"42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"No","scopus_import":"1","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"},{"_id":"GradSch"}]},{"title":"PET – A partial exploration tool for probabilistic verification","author":[{"last_name":"Meggendorfer","first_name":"Tobias","full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1"}],"day":"21","publication":"20th International Symposium on Automated Technology for Verification and Analysis","scopus_import":"1","article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer Nature","department":[{"_id":"KrCh"}],"doi":"10.1007/978-3-031-19992-9_20","quality_controlled":"1","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031199912"],"eisbn":["9783031199929"],"issn":["0302-9743"]},"conference":{"end_date":"2022-10-28","start_date":"2022-10-25","name":"ATVA: Automated Technology for Verification and Analysis","location":"Virtual"},"language":[{"iso":"eng"}],"volume":13505,"date_created":"2023-01-12T12:11:07Z","page":"320-326","month":"10","oa_version":"None","type":"conference","date_updated":"2023-09-05T15:11:51Z","abstract":[{"lang":"eng","text":"We present PET, a specialized and highly optimized framework for partial exploration on probabilistic systems. Over the last decade, several significant advances in the analysis of Markov decision processes employed partial exploration. In a nutshell, this idea allows to focus computation on specific parts of the system, guided by heuristics, while maintaining correctness. In particular, only relevant parts of the system are constructed on demand, which in turn potentially allows to omit constructing large parts of the system. Depending on the model, this leads to dramatic speed-ups, in extreme cases even up to an arbitrary factor. PET unifies several previous implementations and provides a flexible framework to easily implement partial exploration for many further problems. Our experimental evaluation shows significant improvements compared to the previous implementations while vastly reducing the overhead required to add support for additional properties."}],"_id":"12170","acknowledgement":"We thank Pranav Ashok and Maximilian Weininger for their contributions to spiritual predecessors of PET as well as motivating the initial development of this tool.","year":"2022","date_published":"2022-10-21T00:00:00Z","publication_status":"published","intvolume":"     13505","citation":{"apa":"Meggendorfer, T. (2022). PET – A partial exploration tool for probabilistic verification. In <i>20th International Symposium on Automated Technology for Verification and Analysis</i> (Vol. 13505, pp. 320–326). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-19992-9_20\">https://doi.org/10.1007/978-3-031-19992-9_20</a>","mla":"Meggendorfer, Tobias. “PET – A Partial Exploration Tool for Probabilistic Verification.” <i>20th International Symposium on Automated Technology for Verification and Analysis</i>, vol. 13505, Springer Nature, 2022, pp. 320–26, doi:<a href=\"https://doi.org/10.1007/978-3-031-19992-9_20\">10.1007/978-3-031-19992-9_20</a>.","ista":"Meggendorfer T. 2022. PET – A partial exploration tool for probabilistic verification. 20th International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 13505, 320–326.","ama":"Meggendorfer T. PET – A partial exploration tool for probabilistic verification. In: <i>20th International Symposium on Automated Technology for Verification and Analysis</i>. Vol 13505. Springer Nature; 2022:320-326. doi:<a href=\"https://doi.org/10.1007/978-3-031-19992-9_20\">10.1007/978-3-031-19992-9_20</a>","short":"T. Meggendorfer, in:, 20th International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2022, pp. 320–326.","chicago":"Meggendorfer, Tobias. “PET – A Partial Exploration Tool for Probabilistic Verification.” In <i>20th International Symposium on Automated Technology for Verification and Analysis</i>, 13505:320–26. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-031-19992-9_20\">https://doi.org/10.1007/978-3-031-19992-9_20</a>.","ieee":"T. Meggendorfer, “PET – A partial exploration tool for probabilistic verification,” in <i>20th International Symposium on Automated Technology for Verification and Analysis</i>, Virtual, 2022, vol. 13505, pp. 320–326."},"alternative_title":["LNCS"],"status":"public"},{"status":"public","external_id":{"arxiv":["2203.01640"]},"intvolume":"        36","citation":{"ama":"Meggendorfer T. Risk-aware stochastic shortest path. In: <i>Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022</i>. Vol 36. Association for the Advancement of Artificial Intelligence; 2022:9858-9867. doi:<a href=\"https://doi.org/10.1609/aaai.v36i9.21222\">10.1609/aaai.v36i9.21222</a>","ista":"Meggendorfer T. 2022. Risk-aware stochastic shortest path. Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022. Conference on Artificial Intelligence vol. 36, 9858–9867.","mla":"Meggendorfer, Tobias. “Risk-Aware Stochastic Shortest Path.” <i>Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022</i>, vol. 36, no. 9, Association for the Advancement of Artificial Intelligence, 2022, pp. 9858–67, doi:<a href=\"https://doi.org/10.1609/aaai.v36i9.21222\">10.1609/aaai.v36i9.21222</a>.","apa":"Meggendorfer, T. (2022). Risk-aware stochastic shortest path. In <i>Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022</i> (Vol. 36, pp. 9858–9867). Virtual: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v36i9.21222\">https://doi.org/10.1609/aaai.v36i9.21222</a>","ieee":"T. Meggendorfer, “Risk-aware stochastic shortest path,” in <i>Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022</i>, Virtual, 2022, vol. 36, no. 9, pp. 9858–9867.","chicago":"Meggendorfer, Tobias. “Risk-Aware Stochastic Shortest Path.” In <i>Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022</i>, 36:9858–67. Association for the Advancement of Artificial Intelligence, 2022. <a href=\"https://doi.org/10.1609/aaai.v36i9.21222\">https://doi.org/10.1609/aaai.v36i9.21222</a>.","short":"T. Meggendorfer, in:, Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, Association for the Advancement of Artificial Intelligence, 2022, pp. 9858–9867."},"oa":1,"publication_status":"published","date_published":"2022-06-28T00:00:00Z","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2203.01640","open_access":"1"}],"year":"2022","_id":"12568","page":"9858-9867","abstract":[{"text":"We treat the problem of risk-aware control for stochastic shortest path (SSP) on Markov decision processes (MDP). Typically, expectation is considered for SSP, which however is oblivious to the incurred risk. We present an alternative view, instead optimizing conditional value-at-risk (CVaR), an established risk measure. We treat both Markov chains as well as MDP and introduce, through novel insights, two algorithms, based on linear programming and value iteration, respectively. Both algorithms offer precise and provably correct solutions. Evaluation of our prototype implementation shows that risk-aware control is feasible on several moderately sized models.","lang":"eng"}],"date_updated":"2023-02-20T07:19:12Z","type":"conference","oa_version":"Preprint","month":"06","volume":36,"date_created":"2023-02-19T23:00:56Z","conference":{"name":"Conference on Artificial Intelligence","location":"Virtual","start_date":"2022-02-22","end_date":"2022-03-01"},"language":[{"iso":"eng"}],"issue":"9","publication_identifier":{"isbn":["1577358767"],"eissn":["2374-3468"]},"doi":"10.1609/aaai.v36i9.21222","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Association for the Advancement of Artificial Intelligence","department":[{"_id":"KrCh"}],"publication":"Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022","article_processing_charge":"No","scopus_import":"1","author":[{"full_name":"Meggendorfer, Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165","first_name":"Tobias","last_name":"Meggendorfer"}],"day":"28","title":"Risk-aware stochastic shortest path","arxiv":1},{"abstract":[{"lang":"eng","text":"We consider the problem of approximating the reachability probabilities in Markov decision processes (MDP) with uncountable (continuous) state and action spaces. While there are algorithms that, for special classes of such MDP, provide a sequence of approximations converging to the true value in the limit, our aim is to obtain an algorithm with guarantees on the precision of the approximation.\r\nAs this problem is undecidable in general, assumptions on the MDP are necessary. Our main contribution is to identify sufficient assumptions that are as weak as possible, thus approaching the \"boundary\" of which systems can be correctly and reliably analyzed. To this end, we also argue why each of our assumptions is necessary for algorithms based on processing finitely many observations.\r\nWe present two solution variants. The first one provides converging lower bounds under weaker assumptions than typical ones from previous works concerned with guarantees. The second one then utilizes stronger assumptions to additionally provide converging upper bounds. Altogether, we obtain an anytime algorithm, i.e. yielding a sequence of approximants with known and iteratively improving precision, converging to the true value in the limit. Besides, due to the generality of our assumptions, our algorithms are very general templates, readily allowing for various heuristics from literature in contrast to, e.g., a specific discretization algorithm. Our theoretical contribution thus paves the way for future practical improvements without sacrificing correctness guarantees."}],"date_updated":"2023-09-26T10:43:30Z","oa_version":"Published Version","type":"conference","month":"09","date_created":"2023-03-28T08:09:32Z","file_date_updated":"2023-09-26T10:43:15Z","volume":243,"year":"2022","acknowledgement":"Kush Grover: The author has been supported by the DFG research training group GRK\r\n2428 ConVeY.\r\nMaximilian Weininger: The author has been partially supported by DFG projects 383882557\r\nStatistical Unbounded Verification (SUV) and 427755713 Group-By Objectives in Probabilistic\r\nVerification (GOPro)","_id":"12775","has_accepted_license":"1","publication_status":"published","oa":1,"date_published":"2022-09-15T00:00:00Z","ddc":["000"],"external_id":{"arxiv":["2008.04824"]},"status":"public","alternative_title":["LIPIcs"],"citation":{"short":"K. Grover, J. Kretinsky, T. Meggendorfer, M. Weininger, in:, 33rd International Conference on Concurrency Theory , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","chicago":"Grover, Kush, Jan Kretinsky, Tobias Meggendorfer, and Maimilian Weininger. “Anytime Guarantees for Reachability in Uncountable Markov Decision Processes.” In <i>33rd International Conference on Concurrency Theory </i>, Vol. 243. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">https://doi.org/10.4230/LIPIcs.CONCUR.2022.11</a>.","ieee":"K. Grover, J. Kretinsky, T. Meggendorfer, and M. Weininger, “Anytime guarantees for reachability in uncountable Markov decision processes,” in <i>33rd International Conference on Concurrency Theory </i>, Warsaw, Poland, 2022, vol. 243.","apa":"Grover, K., Kretinsky, J., Meggendorfer, T., &#38; Weininger, M. (2022). Anytime guarantees for reachability in uncountable Markov decision processes. In <i>33rd International Conference on Concurrency Theory </i> (Vol. 243). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">https://doi.org/10.4230/LIPIcs.CONCUR.2022.11</a>","mla":"Grover, Kush, et al. “Anytime Guarantees for Reachability in Uncountable Markov Decision Processes.” <i>33rd International Conference on Concurrency Theory </i>, vol. 243, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">10.4230/LIPIcs.CONCUR.2022.11</a>.","ista":"Grover K, Kretinsky J, Meggendorfer T, Weininger M. 2022. Anytime guarantees for reachability in uncountable Markov decision processes. 33rd International Conference on Concurrency Theory . CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 243, 11.","ama":"Grover K, Kretinsky J, Meggendorfer T, Weininger M. Anytime guarantees for reachability in uncountable Markov decision processes. In: <i>33rd International Conference on Concurrency Theory </i>. Vol 243. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">10.4230/LIPIcs.CONCUR.2022.11</a>"},"intvolume":"       243","day":"15","file":[{"file_size":960036,"content_type":"application/pdf","relation":"main_file","creator":"dernst","file_name":"2022_LIPIcS_Grover.pdf","success":1,"date_created":"2023-09-26T10:43:15Z","access_level":"open_access","file_id":"14372","date_updated":"2023-09-26T10:43:15Z","checksum":"e282e43d3ae0ba6e067b72f4583e13c0"}],"author":[{"last_name":"Grover","first_name":"Kush","full_name":"Grover, Kush"},{"first_name":"Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"},{"id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165","full_name":"Meggendorfer, Tobias","first_name":"Tobias","last_name":"Meggendorfer"},{"first_name":"Maimilian","last_name":"Weininger","full_name":"Weininger, Maimilian"}],"title":"Anytime guarantees for reachability in uncountable Markov decision processes","arxiv":1,"article_number":"11","department":[{"_id":"KrCh"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","article_processing_charge":"No","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication":"33rd International Conference on Concurrency Theory ","publication_identifier":{"issn":["1868-8969"]},"quality_controlled":"1","doi":"10.4230/LIPIcs.CONCUR.2022.11","language":[{"iso":"eng"}],"conference":{"start_date":"2022-09-13","name":"CONCUR: Conference on Concurrency Theory","location":"Warsaw, Poland","end_date":"2022-09-16"}},{"intvolume":"     10205","citation":{"short":"J. Kretinsky, T. Meggendorfer, C. Waldmann, M. Weininger, in:, Tools and Algorithms for the Construction and Analysis of Systems, Springer, 2017, pp. 443–460.","chicago":"Kretinsky, Jan, Tobias Meggendorfer, Clara Waldmann, and Maximilian Weininger. “Index Appearance Record for Transforming Rabin Automata into Parity Automata.” In <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, 10205:443–60. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">https://doi.org/10.1007/978-3-662-54577-5_26</a>.","ieee":"J. Kretinsky, T. Meggendorfer, C. Waldmann, and M. Weininger, “Index appearance record for transforming Rabin automata into parity automata,” in <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, Uppsala, Sweden, 2017, vol. 10205, pp. 443–460.","apa":"Kretinsky, J., Meggendorfer, T., Waldmann, C., &#38; Weininger, M. (2017). Index appearance record for transforming Rabin automata into parity automata. In <i>Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 10205, pp. 443–460). Uppsala, Sweden: Springer. <a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">https://doi.org/10.1007/978-3-662-54577-5_26</a>","ista":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2017. Index appearance record for transforming Rabin automata into parity automata. Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10205, 443–460.","mla":"Kretinsky, Jan, et al. “Index Appearance Record for Transforming Rabin Automata into Parity Automata.” <i>Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 10205, Springer, 2017, pp. 443–60, doi:<a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">10.1007/978-3-662-54577-5_26</a>.","ama":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. Index appearance record for transforming Rabin automata into parity automata. In: <i>Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 10205. Springer; 2017:443-460. doi:<a href=\"https://doi.org/10.1007/978-3-662-54577-5_26\">10.1007/978-3-662-54577-5_26</a>"},"alternative_title":["LNCS"],"external_id":{"arxiv":["1701.05738"]},"status":"public","date_published":"2017-03-31T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1701.05738"}],"publication_status":"published","oa":1,"_id":"13160","acknowledgement":"This work is partially funded by the DFG project “Verified Model Checkers” and by the Czech Science Foundation, grant No. P202/12/G061.","year":"2017","volume":10205,"date_created":"2023-06-21T13:21:14Z","page":"443-460","abstract":[{"text":"Transforming deterministic ω\r\n-automata into deterministic parity automata is traditionally done using variants of appearance records. We present a more efficient variant of this approach, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and find out that our method produces smaller automata than previous approaches. Moreover, the experiments demonstrate the potential of our method for LTL synthesis, using LTL-to-Rabin translators. It leads to significantly smaller parity automata when compared to state-of-the-art approaches on complex formulae.","lang":"eng"}],"date_updated":"2023-06-21T13:29:46Z","oa_version":"Preprint","month":"03","type":"conference","conference":{"location":"Uppsala, Sweden","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2017-04-22","end_date":"2017-04-29"},"language":[{"iso":"eng"}],"doi":"10.1007/978-3-662-54577-5_26","quality_controlled":"1","publication_identifier":{"eisbn":["9783662545775"],"isbn":["9783662545768"],"eissn":["1611-3349"],"issn":["0302-9743"]},"publication":"Tools and Algorithms for the Construction and Analysis of Systems","article_processing_charge":"No","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"arxiv":1,"title":"Index appearance record for transforming Rabin automata into parity automata","author":[{"last_name":"Kretinsky","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan"},{"first_name":"Tobias","last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1"},{"first_name":"Clara","last_name":"Waldmann","full_name":"Waldmann, Clara"},{"last_name":"Weininger","first_name":"Maximilian","full_name":"Weininger, Maximilian"}],"day":"31"}]