## Abstract / Description of output

A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multi-type branching processes, stochastic context-free grammars, probabilistic pushdown automata and recursive Markov chains) is the computation of termination probabilities, and computing these probabilities in turn boils down to computing the least fixed point (LFP) solution of a corresponding monotone polynomial system (MPS) of equations, denoted x = P(x).

It was shown by Etessami and Yannakakis [11] that a decomposed variant of Newton’s method converges monotonically to the LFP solution for any MPS that has a non-negative solution. Subsequently, Esparza, Kiefer, and Luttenberger [7] obtained upper bounds on the convergence rate of Newton’s method for certain classes of MPSs. More recently, better upper bounds have been obtained for special classes of MPSs ([10, 9]).

However, prior to this paper, for arbitrary (not necessarily strongly-connected) MPSs, no upper bounds at all were known on the convergence rate of Newton’s method as a function of the encoding size |P| of the input MPS, x = P(x).

In this paper we provide worst-case upper bounds, as a function of both the input encoding size |P|, and ε > 0, on the number of iterations required for decomposed Newton’s method (even with rounding) to converge to within additive error ε > 0 of q *, for an arbitrary MPS with LFP solution q *. Our upper bounds are essentially optimal in terms of several important parameters of the problem.

Using our upper bounds, and building on prior work, we obtain the first P-time algorithm (in the standard Turing model of computation) for quantitative model checking, to within arbitrary desired precision, of discrete-time QBDs and (equivalently) probabilistic 1-counter automata, with respect to any (fixed) ω-regular or LTL property.

It was shown by Etessami and Yannakakis [11] that a decomposed variant of Newton’s method converges monotonically to the LFP solution for any MPS that has a non-negative solution. Subsequently, Esparza, Kiefer, and Luttenberger [7] obtained upper bounds on the convergence rate of Newton’s method for certain classes of MPSs. More recently, better upper bounds have been obtained for special classes of MPSs ([10, 9]).

However, prior to this paper, for arbitrary (not necessarily strongly-connected) MPSs, no upper bounds at all were known on the convergence rate of Newton’s method as a function of the encoding size |P| of the input MPS, x = P(x).

In this paper we provide worst-case upper bounds, as a function of both the input encoding size |P|, and ε > 0, on the number of iterations required for decomposed Newton’s method (even with rounding) to converge to within additive error ε > 0 of q *, for an arbitrary MPS with LFP solution q *. Our upper bounds are essentially optimal in terms of several important parameters of the problem.

Using our upper bounds, and building on prior work, we obtain the first P-time algorithm (in the standard Turing model of computation) for quantitative model checking, to within arbitrary desired precision, of discrete-time QBDs and (equivalently) probabilistic 1-counter automata, with respect to any (fixed) ω-regular or LTL property.

Original language | English |
---|---|

Title of host publication | Computer Aided Verification - 25th International Conference |

Publisher | Springer Berlin Heidelberg |

Pages | 495-510 |

Number of pages | 16 |

ISBN (Electronic) | 978-3-642-39799-8 |

ISBN (Print) | 978-3-642-39798-1 |

DOIs | |

Publication status | Published - 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Berlin Heidelberg |

Volume | 8044 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |