Reference:

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. An extension of Newton's method to -continuous semirings. In Tero Harju, Juhani Karhumäki, and Arto Lepistö, editors, Proceedings of the 11th International Conference on Developments in Language Theory (DLT), volume 4588 of Lecture Notes in Computer Science, pages 157–168, Turku, Finland, 2007. Springer.

Abstract:

Fixed point equations x = F(x) over omega-continuous semirings are a natural mathematical foundation of interprocedural program analysis. Equations over the semiring of the real numbers can be solved numerically using Newton's method. We generalize the method to any omega-continuous semiring and show that it converges faster to the least fixed point than the Kleene sequence 0, F(0), F(F(0)), ... We prove that the Newton approximants in the semiring of languages coincide with finite-index approximations studied by several authors in the 1960s. Finally, we apply our results to the analysis of stochastic context-free grammars.

Suggested BibTeX entry:

@inproceedings{EKL07:dlt,
    address = {Turku, Finland},
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    booktitle = {Proceedings of the 11th International Conference on Developments in Language Theory (DLT)},
    editor = {Tero Harju and Juhani Karhum\"{a}ki and Arto Lepist\"{o}},
    pages = {157--168},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {An Extension of {N}ewton's Method to $\omega$-Continuous Semirings},
    volume = {4588},
    year = {2007}
}