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. doi:10.1016/j.jcss.2014.06.005.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Computer sciences, information science, bioinformatics
Stát vydavatele Nizozemsko
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ěnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 29. 1. 2015 19:00.
Anotace
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 VaVNázev: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Projekty na podporu excelence v základním výzkumu
VytisknoutZobrazeno: 18. 10. 2019 01:49