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