Runtime analysis of probabilistic programs with unbounded recursion

作者：

Highlights：

• We study the runtime in probabilistic programs with unbounded recursion.

• A transformation to make probabilistic PDAs stateless is proposed.

• We give bounds on the probability of long runs of a recursive program.

摘要

•We study the runtime in probabilistic programs with unbounded recursion.•A transformation to make probabilistic PDAs stateless is proposed.•We give bounds on the probability of long runs of a recursive program.

论文关键词：Probabilistic pushdown automata,Recursive Markov chains,Termination time

论文评审过程：Received 21 November 2012, Revised 18 February 2014, Accepted 26 May 2014, Available online 27 June 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.06.005