Putting Newton into Practice: A Solver for Polynomial Equations over Semirings
Putting Newton into Practice: A Solver for Polynomial Equations over Semirings
复制标题
将牛顿付诸实践：半环多项式方程的求解器
DOI：
10.1007/978-3-642-45221-5_48
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Michael Luttenberger
中科院分区：
文献类型：
--
作者：
Maximilian Schlund;Michal Terepeta;Michael Luttenberger
本文给出了求解ω-连续半环上方程组的Newton方法的第一个实现（基于[5，11]）。例如，这样的方程系统自然出现在分析过程间程序或计算数据库的起源。我们的实现提供了一种有吸引力的替代方案，用于在不满足升链条件的某些情况下计算其精确最小解，因此，标准固定点迭代需要与一些过近似（例如，扩展技术）终止。我们提出了一个通用的C++库沿着的主要算法，并分析其复杂性。此外，我们描述了我们的实现的计数半环的基础上半线性集。最后，我们讨论激励的例子以及性能基准。
We present the first implementation of Newton’s method for solving systems of equations overω-continuous semirings (based on [5,11]). For instance, such equation systems arise naturally in the analysis of interprocedural programs or the provenance computation for Datalog. Our implementation provides an attractive alternative for computing their exact least solution in some cases where the ascending chain condition is not met and hence, standard fixed-point iteration needs to be combined with some over-approximation (e.g., widening techniques) to terminate. We present a generic C++ library along with the main algorithms and analyze their complexity. Furthermore, we describe our implementation of the counting semiring based on semilinear sets. Finally, we discuss motivating examples as well as performance benchmarks.
登录
查看更多内容
关于交换半环上的不动点方程
影响因子：
--
作者：
J. Esparza;S. Kiefer;Michael Luttenberger
通讯作者：
Michael Luttenberger
Kleene 代数和字节码验证
DOI：
--
发表时间：
2005
期刊：
Bytecode@ETAPS
影响因子：
--
作者：
Lucja Kot;D. Kozen
通讯作者：
D. Kozen
DOI：
10.1016/j.ic.2015.11.008
发表时间：
2016
期刊：
Inf. Comput.
影响因子：
--
作者：
Michael Luttenberger;Maximilian Schlund
通讯作者：
Maximilian Schlund
帕里克语法图：复杂性和应用
DOI：
10.1109/lics.2010.21
发表时间：
2010
期刊：
2010 25th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Eryk Kopczynski;A. Lin
通讯作者：
A. Lin