License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2023.12
URN: urn:nbn:de:0030-drops-190065
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19006/
Go to the corresponding LIPIcs Volume Portal

Ajdarów, Michal ; Kučera, Antonín

Asymptotic Complexity Estimates for Probabilistic Programs and Their VASS Abstractions

pdf-format:
LIPIcs-CONCUR-2023-12.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{ajdarow_et_al:LIPIcs.CONCUR.2023.12,
  author =	{Ajdar\'{o}w, Michal and Ku\v{c}era, Anton{\'\i}n},
  title =	{{Asymptotic Complexity Estimates for Probabilistic Programs and Their VASS Abstractions}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19006},
  URN =		{urn:nbn:de:0030-drops-190065},
  doi =		{10.4230/LIPIcs.CONCUR.2023.12},
  annote =	{Keywords: Probabilistic programs, asymptotic complexity, vector addition systems}
}

Keywords: Probabilistic programs, asymptotic complexity, vector addition systems
Collection: 34th International Conference on Concurrency Theory (CONCUR 2023)
Issue Date: 2023
Date of publication: 07.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI