Runtime analysis of probabilistic programs with unbounded
recursion

J 2015

Runtime analysis of probabilistic programs with unbounded recursion

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

Základní údaje

Originální název

Runtime analysis of probabilistic programs with unbounded recursion

Autoři

BRÁZDIL, Tomáš (203 Česká republika, domácí), Stefan KIEFER (276 Německo), Antonín KUČERA (203 Česká republika, garant, domácí) a Ivana HUTAŘOVÁ VAŘEKOVÁ (203 Česká republika, domácí)

Vydání

Journal of Computer and System Sciences, Academic Press, 2015, 0022-0000

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

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

Impakt faktor

Impact factor: 1.583

Kód RIV

RIV/00216224:14330/15:00080655

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1016/j.jcss.2014.06.005

UT WoS

000342481400020

Klíčová slova česky

zásobníkové automaty; rekurze

Klíčová slova anglicky

pushdown automata; recursion

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 29. 1. 2015 19:00, prof. RNDr. Antonín Kučera, Ph.D.

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 (pPDAs) which exactly correspond to recursive Markov chains. We show that every pPDA can be transformed into a stateless pPDA (called "pBPA") whose runtime and further properties are closely related to those of the original pPDA. This result substantially simplifies the analysis of runtime and other pPDA properties. We prove that for every pPDA the probability of performing a long run decreases exponentially in the length of the run, if and only if the expected runtime in the pPDA is finite. If the expectation is infinite, then the probability decreases "polynomially". We show that these bounds are asymptotically tight. Our tail bounds on the runtime are generic, i.e., applicable to any probabilistic program with unbounded recursion.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

Citovat

BRÁZDIL, Tomáš, Stefan KIEFER, Antonín KUČERA a Ivana HUTAŘOVÁ VAŘEKOVÁ. Runtime analysis of probabilistic programs with unbounded recursion. Journal of Computer and System Sciences. Academic Press, 2015, roč. 81, č. 1, s. 288-310. ISSN 0022-0000. Dostupné z: https://dx.doi.org/10.1016/j.jcss.2014.06.005.

@article{1219109,
   author = {Brázdil, Tomáš and Kiefer, Stefan and Kučera, Antonín and Hutařová Vařeková, Ivana},
   article_number = {1},
   doi = {http://dx.doi.org/10.1016/j.jcss.2014.06.005},
   keywords = {pushdown automata; recursion},
   language = {eng},
   issn = {0022-0000},
   journal = {Journal of Computer and System Sciences},
   title = {Runtime analysis of probabilistic programs with unbounded recursion},
   volume = {81},
   year = {2015}
}

TY  - JOUR
ID  - 1219109
AU  - Brázdil, Tomáš - Kiefer, Stefan - Kučera, Antonín - Hutařová Vařeková, Ivana
PY  - 2015
TI  - Runtime analysis of probabilistic programs with unbounded recursion
JF  - Journal of Computer and System Sciences
VL  - 81
IS  - 1
SP  - 288-310
EP  - 288-310
PB  - Academic Press
SN  - 00220000
KW  - pushdown automata
KW  - recursion
N2  - We study the runtime in probabilistic programs with unbounded recursion. As underlying formal model for such programs we use probabilistic pushdown automata (pPDAs) which exactly correspond to recursive Markov chains. We show that every pPDA can be transformed into a stateless pPDA (called "pBPA") whose runtime and further properties are closely related to those of the original pPDA. This result substantially simplifies the analysis of runtime and other pPDA properties. We prove that for every pPDA the probability of performing a long run decreases exponentially in the length of the run, if and only if the expected runtime in the pPDA is finite. If the expectation is infinite, then the probability decreases "polynomially". We show that these bounds are asymptotically tight. Our tail bounds on the runtime are generic, i.e., applicable to any probabilistic program with unbounded recursion.
ER  -

BRÁZDIL, Tomáš, Stefan KIEFER, Antonín KUČERA a Ivana HUTAŘOVÁ VAŘEKOVÁ. Runtime analysis of probabilistic programs with unbounded recursion. \textit{Journal of Computer and System Sciences}. Academic Press, 2015, roč.~81, č.~1, s.~288-310. ISSN~0022-0000. Dostupné z: https://dx.doi.org/10.1016/j.jcss.2014.06.005.

Podrobný výpis o publikaci