| Identifikační kód | RIV/00216224:14330/15:00080655 |
|---|
| Název v anglickém jazyce | Runtime analysis of probabilistic programs with unbounded recursion |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 3 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Tomáš Brázdil (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 1762834)
Stefan Kiefer (státní příslušnost: DE - Spolková republika Německo)
Antonín Kučera (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 9872655)
Ivana Hutařová Vařeková (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7198736) |
|---|
| Popis výsledku v anglickém jazyce | 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 theprobability 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 areasymptotically tight. Our tail bounds on the runtime are generic, i.e., applicable to any probabilistic program with unbounded recursion. |
|---|
| Klíčová slova oddělená středníkem | pushdown automata; recursion |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1016/j.jcss.2014.06.005 |
|---|