Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00131636" target="_blank" >RIV/00216224:14330/23:00131636 - isvavai.cz</a>
Result on the web
<a href="https://drops.dagstuhl.de/opus/volltexte/2023/19006/" target="_blank" >https://drops.dagstuhl.de/opus/volltexte/2023/19006/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CONCUR.2023.12" target="_blank" >10.4230/LIPIcs.CONCUR.2023.12</a>
Alternative languages
Result language
angličtina
Original language name
Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions
Original language 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10200 - Computer and information sciences
Result continuities
Project
<a href="/en/project/GA21-24711S" target="_blank" >GA21-24711S: Efficient Analysis and Optimization for Probabilistic Systems and Games</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
34th International Conference on Concurrency Theory (CONCUR 2023)
ISBN
9783959772990
ISSN
1868-8969
e-ISSN
—
Number of pages
16
Pages from-to
„12:1“-„12:16“
Publisher name
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Antwerp, Belgium
Event date
Jan 1, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—