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 et al., editor, Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), part II, 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), part II},
    editor = {Luca Aceto et al.},
    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}
}

PDF (140 kB)