I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Newtonian Program Analysis

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}
}

Tech report version
This work is not available online here.