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 LNCS, 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 = {LNCS},
    title = {Newton's Method for $\omega$-Continuous Semirings},
    volume = {5126},
    year = {2008}
}

GZipped PostScript (113 kB)
PDF (140 kB)