An Extension of Newton ’ s Method to ω-Continuous Semirings ?
An Extension of Newton ’ s Method to ω-Continuous Semirings ?
复制标题
牛顿法对 ω-连续半环的扩展？
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Michael Luttenberger
中科院分区：
文献类型：
--
作者：
J. Esparza;S. Kiefer;Michael Luttenberger
ω-连续半环上的不动点方程x=F(X)是程序间分析的自然数学基础。实数半环上的方程可以用牛顿方法进行数值求解。我们将该方法推广到任意ω-连续半环，证明了它比Kleene序列0，F(0)，F(F(0))收敛到最小不动点更快。。。我们证明了语言半环中的牛顿逼近与20世纪60年代几位作者研究的有限指数逼近重合。最后，我们将我们的结果应用于随机上下文无关文法的分析。
Fixed point equations x = F (x) over ω-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 ω-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 finiteindex approximations studied by several authors in the 1960s. Finally, we apply our results to the analysis of stochastic context-free grammars.