Runtime Analysis of Probabilistic Programs with Unbounded Recursion

BRÁZDIL, Tomáš; Stefan KIEFER; Antonín KUČERA a Ivana HUTAŘOVÁ VAŘEKOVÁ. Runtime Analysis of Probabilistic Programs with Unbounded Recursion. In Luca Aceto, Monika Henzinger, Jiří Sgall. Proceedings of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011). Berlin: Springer, 2011, s. 319-331. ISBN 978-3-642-22011-1.

Základní údaje

Originální název

Runtime Analysis of Probabilistic Programs with Unbounded Recursion

Autoři

BRÁZDIL, Tomáš; Stefan KIEFER; Antonín KUČERA a Ivana HUTAŘOVÁ VAŘEKOVÁ ORCID

Vydání

Berlin, Proceedings of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), od s. 319-331, 13 s. 2011

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/11:00049980

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-22011-1

UT WoS

000342481400020

Klíčová slova anglicky

pushdown automata; probabilistic systems; termination

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

We study the runtime in probabilistic programs with unbounded recursion. As underlying formal model for such programs we use probabilistic pushdown automata (pPDA) which exactly correspond to recursive Markov chains.

Česky

V článku se zkoumají pravděpodobnostní systémy s neomezenou hloubkou rekurze. Jako matematický model těchto systémů jsou použity pravděpodobnostní zásobníkové automaty, které přesně odpovídají rekurzivním Markovovským procesům.

---

Návaznosti

GAP202/10/1469, projekt VaV	Název: Formální metody pro analýzu a verifikaci komplexních systémů Investor: Grantová agentura ČR, Formální metody pro analýzu a verifikaci komplexních systémů
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
MUNI/A/0914/2009, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky