Reference:

M. Luttenberger and M. Schlund. Convergence of Newton's Method over Commutative Semirings. In LATA, volume 7810 of Lecture Notes in Computer Science, pages 407–418, April 2013.

Abstract:

We give a lower bound on the speed at which Newton's method (as defined in iteEKL07:dlt,EKL07:stacs) converges over arbitrary -continuous commutative semirings. From this result, we deduce that Newton's method converges within a finite number of iterations over any semiring which is ``collapsed at some '' (i.e. holds) in the sense of iteDBLP:journals/iandc/BloomE09. We apply these results to (1) obtain a generalization of Parikh's theorem, (2) to compute the provenance of Datalog queries, and (3) to analyze weighted pushdown systems. We further show how to compute Newton's method over any -continuous semiring.

Suggested BibTeX entry:

@inproceedings{DBLP:conflataLuttenbergerS13,
    author = {M. Luttenberger and M. Schlund},
    booktitle = {LATA},
    month = {April},
    pages = {407--418},
    series = {Lecture Notes in Computer Science},
    title = {Convergence of {N}ewton's {M}ethod over {C}ommutative {S}emirings},
    volume = {7810},
    year = {2013}
}