Runtime Analysis of Probabilistic Programs with Unbounded Recursion

Details Runtime Analysis of Probabilistic Programs with Unbounded Recursion Runtime Analysis of Probabilistic Programs with Unbounded Recursion

2010-07-10

arxiv.org/abs/1007.1710v1

Computer Science

Logic in Computer Science

Scientific paper

We study termination time and recurrence time in programs with unbounded recursion, which are either randomized or operate on some statistically quantified inputs. As the underlying formal model for such programs we use probabilistic pushdown automata (pPDA) which are equivalent to probabilistic recursive state machines. We obtain tail bounds for the distribution of termination time for pPDA. We also study the recurrence time for probabilistic recursive programs that are not supposed to terminate (such as system daemons, network servers, etc.). Typically, such programs react to certain requests generated by their environment, and hence operate in finite request-service cycles. We obtain bounds for the frequency of long request-service cycles.

Affiliated with

Also associated with

No associations

Rating

Runtime Analysis of Probabilistic Programs with Unbounded Recursion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Runtime Analysis of Probabilistic Programs with Unbounded Recursion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Runtime Analysis of Probabilistic Programs with Unbounded Recursion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-300314