Runtime Analysis of Probabilistic Programs with Unbounded Recursion

Brázdil,  Tomáš; Kiefer, Stefan; Kučera,  Antonín; Hutařová Vařeková,  Ivana

Runtime Analysis of Probabilistic Programs with Unbounded Recursion

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	BRÁZDIL Tomáš KIEFER Stefan KUČERA Antonín HUTAŘOVÁ VAŘEKOVÁ Ivana
Year of publication	2011
Type	Article in Proceedings
Conference	Proceedings of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)
MU Faculty or unit	Faculty of Informatics
Citation
Field	Informatics
Keywords	pushdown automata; probabilistic systems; termination
Description	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.
Related projects:	Institute for Theoretical Computer Science Highly Parallel and Distributed Computing Systems Formální metody pro analýzu a verifikaci komplexních systémů Rozsáhlé výpočetní systémy: modely, aplikace a verifikace