Newtonian program analysisNewtonian program analysis

Access Restriction
Subscribed

 Author Esparza, Javier ♦ Kiefer, Stefan ♦ Luttenberger, Michael Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2010 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Newton's method ♦ Interprocedural program analysis ♦ Polynomial fixed-point equations ♦ Semirings Abstract 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 ω-continuous semirings. Complete semilattices, the common program analysis framework, are a special class of ω-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 $\textit{n}$ equations is at most $\textit{n}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-11-05 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 57 Issue Number 6 Page Count 47 Starting Page 1 Ending Page 47

Open content in new tab

Source: ACM Digital Library