{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T11:14:18Z","timestamp":1753182858035,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T00:00:00Z","timestamp":1441929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000188","name":"Royal Society","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000188","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,9,11]]},"abstract":"<jats:p>\n            A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multitype 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\n            <jats:italic>x<\/jats:italic>\n            =\n            <jats:italic>P<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>It was shown in Etessami and Yannakakis [2009] that a decomposed variant of Newton\u2019s method converges monotonically to the LFP solution for any MPS that has a nonnegative solution. Subsequently, Esparza et al. [2010] obtained upper bounds on the convergence rate of Newton\u2019s method for certain classes of MPSs. More recently, better upper bounds have been obtained for special classes of MPSs [Etessami et al. 2010, 2012].<\/jats:p>\n          <jats:p>\n            However, prior to this article, for arbitrary (not necessarily strongly connected) MPSs, no upper bounds at all were known on the convergence rate of Newton\u2019s method as a function of the encoding size |P| of the input MPS,\n            <jats:italic>x<\/jats:italic>\n            =\n            <jats:italic>P<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            In this article, we provide worst-case upper bounds, as a function of both the input encoding size |P|, and\n            <jats:italic>\u03b5<\/jats:italic>\n            &gt; 0, on the number of iterations required for decomposed Newton\u2019s method (even with rounding) to converge to within additive error\n            <jats:italic>\u03b5<\/jats:italic>\n            &gt; 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.\n          <\/jats:p>\n          <jats:p>\n            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)\n            <jats:italic>\u03c9<\/jats:italic>\n            -regular or LTL property.\n          <\/jats:p>","DOI":"10.1145\/2789208","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T12:09:15Z","timestamp":1442318955000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Upper Bounds for Newton\u2019s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata"],"prefix":"10.1145","volume":"62","author":[{"given":"Alistair","family":"Stewart","sequence":"first","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kousha","family":"Etessami","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,9,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_2_1_3_1","volume-title":"Mathematical Analysis","author":"Apostol T.","unstructured":"T. Apostol. 1974. Mathematical Analysis (2nd ed.). Addison-Wesley.","edition":"2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","unstructured":"D. Bini G. Latouche and B. Meini. 2005. Numerical Methods for Structured Markov Chains. Oxford University Press.","DOI":"10.5555\/1121577"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032305.2032323"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629599"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210339"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"R. Durbin S. R. Eddy A. Krogh and G. Mitchison. 1999. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.","DOI":"10.1017\/CBO9780511790492"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/090749591"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Model checking probabilistic pushdown automata","volume":"2","author":"Esparza J.","year":"2006","unstructured":"J. Esparza, A. Ku\u010dera, and R. Mayr. 2006. Model checking probabilistic pushdown automata. Log. Meth. Comput. Sci. 2, 1, 1--31.","journal-title":"Log. Meth. Comput. Sci."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214030"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2009.12.009"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462154"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2159531.2159534"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993665"},{"volume-title":"The Theory of Branching Processes","author":"Harris T. E.","key":"e_1_2_1_16_1","unstructured":"T. E. Harris. 1963. The Theory of Branching Processes. Springer-Verlag."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","unstructured":"R. A. Horn and C. R. Johnson. 1985. Matrix Analysis. Cambridge University Press.","DOI":"10.5555\/5509"},{"key":"e_1_2_1_18_1","unstructured":"E. Isaacson and H. B. Keller. 1966. Analysis of Numerical Methods. Wiley."},{"key":"e_1_2_1_19_1","unstructured":"P. Lancaster and M. Tismenetsky. 1985. The Theory of Matrices (2nd ed.). Academic Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"G. Latouche and V. Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability.","DOI":"10.1137\/1.9780898719734"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-009-9062-1"},{"volume-title":"Matrix-Geometric Solutions in Stochastic Models: An algorithmic approach","author":"Neuts M. F.","key":"e_1_2_1_22_1","unstructured":"M. F. Neuts. 1981. Matrix-Geometric Solutions in Stochastic Models: An algorithmic approach. Johns Hopkins University Press."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958031.2958113"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763507.1763517"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2789208","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2789208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:05Z","timestamp":1750223225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2789208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,11]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,9,11]]}},"alternative-id":["10.1145\/2789208"],"URL":"https:\/\/doi.org\/10.1145\/2789208","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2015,9,11]]},"assertion":[{"value":"2014-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}