Efficient Analysis of Probabilistic Programs with an Unbounded Counter

Computer Science – Formal Languages and Automata Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

We show that a subclass of infinite-state probabilistic programs that can be modeled by probabilistic one-counter automata (pOC) admits an efficient quantitative analysis. In particular, we show that the expected termination time can be approximated up to an arbitrarily small relative error with polynomially many arithmetic operations, and the same holds for the probability of all runs that satisfy a given omega-regular property. Further, our results establish a powerful link between pOC and martingale theory, which leads to fundamental observations about quantitative properties of runs in pOC. In particular, we provide a "divergence gap theorem", which bounds a positive non-termination probability in pOC away from zero.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Efficient Analysis of Probabilistic Programs with an Unbounded Counter 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 Efficient Analysis of Probabilistic Programs with an Unbounded Counter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Analysis of Probabilistic Programs with an Unbounded Counter will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-84965

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.