I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Convergence of Newton's Method over Commutative Semirings


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.


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:

    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}

PDF (367 kB)