We give a lower bound on the speed at which Newton’s method (as defined in [5,6]) 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.
+ 1 holds) in the sense of . 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