Newton ’ s Method for ω-Continuous Semirings ⋆
Newton ’ s Method for ω-Continuous Semirings ⋆
复制标题
ω-连续半环的牛顿法 ⋆
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Michael Luttenberger
中科院分区：
文献类型：
--
作者：
J. Esparza;S. Kiefer;Michael Luttenberger
不动点方程X = f (X)过ω-连续半环是程序间程序分析的自然数学基础。求解这些方程的一般算法基于Kleene定理，该定理表明序列0，f (0), f (f(0))，…收敛到最小不动点。然而，这种方法通常效率低下。本文报道了将数值数学中著名的牛顿方法推广到任意ω-连续半环的最新工作，并分析了其在实际半环中的收敛速度。
Fixed point equations X = f (X) overω-continuous semirings are a natural mathematical foundation of interprocedural program analysis . Generic algorithms for solving these equations are based on Kleene’s theorem, wh ich 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 wh ich we extend Newton’s method, the well-known technique from numerical mathe matics, to arbitraryω-continuous semirings, and analyze its convergence speed in the real semiring.