Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata

Alistair Stewart, Kousha Etessami, Mihalis Yannakakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationComputer Aided Verification - 25th International Conference
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-642-39799-8
ISBN (Print)978-3-642-39798-1
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Upper Bounds for Newton's Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata'. Together they form a unique fingerprint.

Cite this