Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
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. Technical report, Technische Universität München, Institut für Informatik, April 2009. An improved version of this report will be published in JACM.

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. Furthermore, the number of iterations required to solve a system of n equations is at most n.

Suggested BibTeX entry:

@techreport{EKL09:newtProgAn,
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
    month = {April},
    note = {An improved version of this report will be published in JACM},
    title = {Newtonian Program Analysis},
    year = {2009}
}

PDF (422 kB)