Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

<a href="/cs/project/GA21-24711S" target="_blank" >GA21-24711S: Efektivní analýza a optimalizace pravděpodobnostních systémů a her</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

34th International Conference on Concurrency Theory (CONCUR 2023)

ISBN

9783959772990

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

16

Strana od-do

„12:1“-„12:16“

Název nakladatele

Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Antwerp, Belgium

Datum konání akce

1. 1. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—