Runtime Analysis of Probabilistic Programs with Unbounded Recursion

• 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
• 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