Other formats:
BibTeX
LaTeX
RIS
@inproceedings{2308407, author = {Ajdarów, Michal and Kučera, Antonín}, address = {Dagstuhl, Germany}, booktitle = {34th International Conference on Concurrency Theory (CONCUR 2023)}, doi = {http://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12}, editor = {Perez, Guillermo A. and Raskin, Jean-Francois}, keywords = {VASS; termination complexity}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Dagstuhl, Germany}, isbn = {978-3-95977-299-0}, pages = {"12:1"-"12:16"}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik}, title = {Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions}, url = {https://drops.dagstuhl.de/opus/volltexte/2023/19006/}, year = {2023} }
TY - JOUR ID - 2308407 AU - Ajdarów, Michal - Kučera, Antonín PY - 2023 TI - Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions PB - Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany SN - 9783959772990 KW - VASS KW - termination complexity UR - https://drops.dagstuhl.de/opus/volltexte/2023/19006/ N2 - 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. ER -
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. \textit{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.
|