Další formáty:
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 a 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, s.~''12:1''-''12:16'', 16 s. ISBN~978-3-95977-299-0. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12.
|
