Asymptotic Complexity Estimates for Probabilistic Programs and
their VASS Abstractions

D 2023

Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

AJDARÓW, Michal and Antonín KUČERA

Basic information

Original name

Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Authors

AJDARÓW, Michal (203 Czech Republic, belonging to the institution) and Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution)

Edition

Dagstuhl, Germany, 34th International Conference on Concurrency Theory (CONCUR 2023), p. "12:1"-"12:16", 16 pp. 2023

Publisher

Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

Dagstuhl website

RIV identification code

RIV/00216224:14330/23:00131636

Organization unit

Faculty of Informatics

ISBN

978-3-95977-299-0

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12

Keywords (in Czech)

VASS; výpočetní složitost

Keywords in English

VASS; termination complexity

Abstract

V originále

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.

Links

GA21-24711S, research and development project

Name: Efektivní analýza a optimalizace pravděpodobnostních systémů a her (Acronym: Efektivní analýza a optimalizace pravděpodobnostní)

Investor: Czech Science Foundation

MUNI/A/1081/2022, interní kód MU

Name: Modelování, analýza a verifikace (2023)

Investor: Masaryk University

MUNI/A/1433/2022, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23

Investor: Masaryk University

Citovat

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. 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.

@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.

Detailed Information on Publication Record