Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

AJDARÓW Michal KUČERA Antonín

Rok publikování 2023
Druh Článek ve sborníku
Konference 34th International Conference on Concurrency Theory (CONCUR 2023)
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www Dagstuhl website
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12
Klíčová slova VASS; termination complexity
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.