TY - GEN
T1 - Convergence of newton's method over commutative semirings
AU - Luttenberger, Michael
AU - Schlund, Maximilian
N1 - Funding Information:
This work was partially funded by the DFG project “Polynomial Systems on Semirings: Foundations, Algorithms, Applications”.
PY - 2013
Y1 - 2013
N2 - 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 k ∈ ℕ" (i.e. k = k + 1 holds) in the sense of [1]. 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.
AB - 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 k ∈ ℕ" (i.e. k = k + 1 holds) in the sense of [1]. 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.
UR - http://www.scopus.com/inward/record.url?scp=84875643299&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-37064-9_36
DO - 10.1007/978-3-642-37064-9_36
M3 - Conference contribution
AN - SCOPUS:84875643299
SN - 9783642370632
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 407
EP - 418
BT - Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings
PB - Springer Verlag
T2 - 7th International Conference on Language and Automata Theory and Applications, LATA 2013
Y2 - 2 April 2013 through 5 April 2013
ER -