Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

AJDARÓW Michal KUČERA Antonín

Year of publication 2023
Type Article in Proceedings
Conference 34th International Conference on Concurrency Theory (CONCUR 2023)
MU Faculty or unit

Faculty of Informatics

Citation
Web Dagstuhl website
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12
Keywords VASS; termination complexity
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.