




Publications  An Extension of Newton's Method to omegaContinuous Semirings





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 omegacontinuous 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 omegacontinuous 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 finiteindex approximations studied by several authors in the 1960s. Finally, we apply our results to the analysis of stochastic contextfree 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}
}




