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

A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multi-typ…