{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T02:11:01Z","timestamp":1789179061226,"version":"build-2803163510"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T00:00:00Z","timestamp":1285891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>\n            This article presents a novel generic technique for solving dataflow equations in interprocedural dataflow analysis. The technique is obtained by generalizing Newton's method for computing a zero of a differentiable function to \u03c9-continuous semirings. Complete semilattices, the common program analysis framework, are a special class of \u03c9-continuous semirings. We show that our generalized method always converges to the solution, and requires at most as many iterations as current methods based on Kleene's fixed-point theorem. We also show that, contrary to Kleene's method, Newton's method always terminates for arbitrary idempotent and commutative semirings. More precisely, in the latter setting the number of iterations required to solve a system of\n            <jats:italic>n<\/jats:italic>\n            equations is at most\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/1857914.1857917","type":"journal-article","created":{"date-parts":[[2010,11,3]],"date-time":"2010-11-03T14:16:37Z","timestamp":1288793797000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Newtonian program analysis"],"prefix":"10.1145","volume":"57","author":[{"given":"Javier","family":"Esparza","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Kiefer","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Luttenberger","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,11,5]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"200","article-title":"A fully equational proof of Parikh's theorem. RAIRO","volume":"36","author":"Aceto L.","year":"2001","unstructured":"Aceto , L. , \u00c9sik , Z. , and Ing\u00f3lfsd\u00f3ttir , A. 2001 . A fully equational proof of Parikh's theorem. RAIRO , Theoretical Informatics and Applications 36 , 200 -- 202 . Aceto, L., \u00c9sik, Z., and Ing\u00f3lfsd\u00f3ttir, A. 2001. A fully equational proof of Parikh's theorem. RAIRO, Theoretical Informatics and Applications 36, 200--2.","journal-title":"Theoretical Informatics and Applications"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.19"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178263"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of Conference on Developments in Language Theory. LNCS 4588","author":"Esparza J.","unstructured":"Esparza , J. , Kiefer , S. , and Luttenberger , M . 2007a. An extension of Newton's method to \u03c9-continuous semirings . In Proceedings of Conference on Developments in Language Theory. LNCS 4588 . Springer, 157--168. Esparza, J., Kiefer, S., and Luttenberger, M. 2007a. An extension of Newton's method to \u03c9-continuous semirings. In Proceedings of Conference on Developments in Language Theory. LNCS 4588. Springer, 157--168."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of Symposium on Theoretical Aspects of Computer Science. LNCS 4397","author":"Esparza J.","unstructured":"Esparza , J. , Kiefer , S. , and Luttenberger , M . 2007b. On fixed point equations over commutative semirings . In Proceedings of Symposium on Theoretical Aspects of Computer Science. LNCS 4397 . Springer, 296--307. Esparza, J., Kiefer, S., and Luttenberger, M. 2007b. On fixed point equations over commutative semirings. In Proceedings of Symposium on Theoretical Aspects of Computer Science. LNCS 4397. Springer, 296--307."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of Symposium on Theoretical Aspects of Computer Science. 289--300","author":"Esparza J.","unstructured":"Esparza , J. , Kiefer , S. , and Luttenberger , M . 2008. Convergence thresholds of Newton's method for monotone polynomial equations . In Proceedings of Symposium on Theoretical Aspects of Computer Science. 289--300 . Esparza, J., Kiefer, S., and Luttenberger, M. 2008. Convergence thresholds of Newton's method for monotone polynomial equations. In Proceedings of Symposium on Theoretical Aspects of Computer Science. 289--300."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/090749591"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.39"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021838"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462154"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of Symposium on Logic in Computer Science. 394--401","author":"Hopkins M. W.","unstructured":"Hopkins , M. W. , and Kozen , D . 1999. Parikh's theorem in commutative Kleene algebra . In Proceedings of Symposium on Logic in Computer Science. 394--401 . Hopkins, M. W., and Kozen, D. 1999. Parikh's theorem in commutative Kleene algebra. In Proceedings of Symposium on Logic in Computer Science. 394--401."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/582153.582161"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290339"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250822"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512945"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Conference on Compiler Construction. LNCS","volume":"641","author":"Knoop J.","unstructured":"Knoop , J. and Steffen , B . 1992. The interprocedural coincidence theorem . In Proceedings of the International Conference on Compiler Construction. LNCS , vol. 641 . Springer, 125--140. Knoop, J. and Steffen, B. 1992. The interprocedural coincidence theorem. In Proceedings of the International Conference on Compiler Construction. LNCS, vol. 641. Springer, 125--140."},{"key":"e_1_2_1_19_1","volume-title":"Handbook of Formal Languages","author":"Kuich W.","unstructured":"Kuich , W. 1997. Handbook of Formal Languages . Vol. 1 . Springer , Chapter 9: Semirings and Formal Power Series: Their Relevance to Formal Languages and Automata, 609--677. Kuich, W. 1997. Handbook of Formal Languages. Vol. 1. Springer, Chapter 9: Semirings and Formal Power Series: Their Relevance to Formal Languages and Automata, 609--677."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Nielson F. Nielson H. and Hankin C. 1999. Principles of Program Analysis. Springer.   Nielson F. Nielson H. and Hankin C. 1999. Principles of Program Analysis. Springer.","DOI":"10.1007\/978-3-662-03811-6"},{"key":"e_1_2_1_21_1","volume-title":"Numerical Analysis: A Second Course","author":"Ortega J.","year":"1972","unstructured":"Ortega , J. 1972 . Numerical Analysis: A Second Course . Academic Press , New York . Ortega, J. 1972. Numerical Analysis: A Second Course. Academic Press, New York."},{"key":"e_1_2_1_22_1","unstructured":"Ortega J. and Rheinboldt W. 1970. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press.  Ortega J. and Rheinboldt W. 1970. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.02.009"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00072-2"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00058-8"},{"key":"e_1_2_1_27_1","unstructured":"Sharir M. and Pnueli A. 1981. Program Flow Analysis: Theory and Applications. Prentice-Hall Chapter 7: Two Approaches to Interprocedural Data Flow Analysis 189--233.  Sharir M. and Pnueli A. 1981. Program Flow Analysis: Theory and Applications. Prentice-Hall Chapter 7: Two Approaches to Interprocedural Data Flow Analysis 189--233."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857914.1857917","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1857914.1857917","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:09:10Z","timestamp":1750248550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857914.1857917"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1145\/1857914.1857917"],"URL":"https:\/\/doi.org\/10.1145\/1857914.1857917","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}