Reference:

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Newtonian program analysis. Journal of the ACM, 57(6):33:1–33:47, October 2010.

Abstract:

This paper 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 omega-continuous semirings. Complete semilattices, the common program analysis framework, are a special class of omega-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 equations is at most n.

Suggested BibTeX entry:

@article{EKL10:newtProgAn,
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    journal = {Journal of the ACM},
    month = {October},
    number = {6},
    pages = {33:1--33:47},
    title = {Newtonian Program Analysis},
    volume = {57},
    year = {2010}
}