Reference:

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. An extension of Newton's method to -continuous semirings. Technical report, Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, March 2007.

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:

@techreport{EKL07:dltTechRep,
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    institution = {Universit\"{a}t Stuttgart, Fakult\"{a}t Informatik, Elektrotechnik und Informationstechnik},
    month = {March},
    title = {An Extension of {N}ewton's Method to $\omega$-Continuous Semirings},
    year = {2007}
}