TY - GEN
T1 - Putting Newton into practice
T2 - 19th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2013
AU - Schlund, Maximilian
AU - Terepeta, Michał
AU - Luttenberger, Michael
N1 - Funding Information:
This work was partially funded by the DFG project “Polynomial Systems on Semirings: Foundations, Algorithms, Applications” and MT-LAB ( http://www.mt- lab.dk/ ).
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893956184&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45221-5_48
DO - 10.1007/978-3-642-45221-5_48
M3 - Conference contribution
AN - SCOPUS:84893956184
SN - 9783642452208
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 727
EP - 734
BT - Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings
Y2 - 14 December 2013 through 19 December 2013
ER -