AJDARÓW, Michal and Antonín KUČERA. Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions. Online. In Perez, Guillermo A. and Raskin, Jean-Francois. 34th International Conference on Concurrency Theory (CONCUR 2023). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, 2023, p. "12:1"-"12:16", 16 pp. ISBN 978-3-95977-299-0. Available from: https://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions
Authors AJDARÓW, Michal (203 Czech Republic, belonging to the institution) and Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution).
Edition Dagstuhl, Germany, 34th International Conference on Concurrency Theory (CONCUR 2023), p. "12:1"-"12:16", 16 pp. 2023.
Publisher Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10200 1.2 Computer and information sciences
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW Dagstuhl website
RIV identification code RIV/00216224:14330/23:00131636
Organization unit Faculty of Informatics
ISBN 978-3-95977-299-0
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12
Keywords (in Czech) VASS; výpočetní složitost
Keywords in English VASS; termination complexity
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 7/4/2024 23:20.
Abstract
The standard approach to analyzing the asymptotic complexity of probabilistic programs is based on studying the asymptotic growth of certain expected values (such as the expected termination time) for increasing input size. We argue that this approach is not sufficiently robust, especially in situations when the expectations are infinite. We propose new estimates for the asymptotic analysis of probabilistic programs with non-deterministic choice that overcome this deficiency. Furthermore, we show how to efficiently compute/analyze these estimates for selected classes of programs represented as Markov decision processes over vector addition systems with states.
Links
GA21-24711S, research and development projectName: Efektivní analýza a optimalizace pravděpodobnostních systémů a her (Acronym: Efektivní analýza a optimalizace pravděpodobnostní)
Investor: Czech Science Foundation
MUNI/A/1081/2022, interní kód MUName: Modelování, analýza a verifikace (2023)
Investor: Masaryk University
MUNI/A/1433/2022, interní kód MUName: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23
Investor: Masaryk University
PrintDisplayed: 3/9/2024 16:52