Chair for Foundations of Software Reliability and Theoretical Computer Science
 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,
title = {Newton's Method for $\omega$-Continuous Semirings},