D 2023

Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

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

Základní údaje

Originální název

Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions

Autoři

AJDARÓW, Michal (203 Česká republika, domácí) a Antonín KUČERA (203 Česká republika, garant, domácí)

Vydání

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

Nakladatel

Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

Kód RIV

RIV/00216224:14330/23:00131636

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-299-0

ISSN

DOI

Klíčová slova česky

VASS; výpočetní složitost

Klíčová slova anglicky

VASS; termination complexity

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 7. 4. 2024 23:20, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

GA21-24711S, projekt VaV
Název: Efektivní analýza a optimalizace pravděpodobnostních systémů a her (Akronym: Efektivní analýza a optimalizace pravděpodobnostní)
Investor: Grantová agentura ČR, Efektivní analýza a optimalizace pravděpodobnostních systémů a her
MUNI/A/1081/2022, interní kód MU
Název: Modelování, analýza a verifikace (2023)
Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)
MUNI/A/1433/2022, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23