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 - Newton's Method for omega-Continuous Semirings

Reference:

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Newton's method for -continuous semirings. In Luca Aceto, Magnus M. Halldorsson, and Anna Ingolfsdottir, editors, Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), volume 5126 of Lecture Notes in Computer Science, pages 14–26, Reykjavik, Iceland, 2008. Springer. Invited paper.

Abstract:

Fixed point equations X = f(X) over omega-continuous semirings are a natural mathematical foundation of interprocedural program analysis. Generic algorithms for solving these equations are based on Kleene's theorem, which states that the sequence 0, f(0), f(f(0)), ... converges to the least fixed point. However, this approach is often inefficient. We report on recent work in which we extend Newton's method, the well-known technique from numerical mathematics, to arbitrary omega-continuous semirings, and analyze its convergence speed in the real semiring.

Suggested BibTeX entry:

@inproceedings{EKL08:icalp,
    address = {Reykjavik, Iceland},
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    booktitle = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP)},
    editor = {Luca Aceto and Magnus M. Halldorsson and Anna Ingolfsdottir},
    note = {Invited paper},
    pages = {14--26},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {Newton's Method for $\omega$-Continuous Semirings},
    volume = {5126},
    year = {2008}
}

GZipped PostScript (113 kB)
PDF (140 kB)