文摘
We give a lower bound on the speed at which Newton's method (as defined in [11]) converges over arbitrary m>ω m>-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 mmlsi1" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0890540115001194&_mathId=si1.gif&_user=111111111&_pii=S0890540115001194&_rdoc=1&_issn=08905401&md5=e39fc684b73bd135109c12fc21d3750c" title="Click to view the MathML source">k∈NmathContainer hidden">mathCode"><math altimg="si1.gif" overflow="scroll"><mi>kmi><mo>∈mo><mi mathvariant="double-struck">Nmi>math>” (i.e. mmlsi2" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0890540115001194&_mathId=si2.gif&_user=111111111&_pii=S0890540115001194&_rdoc=1&_issn=08905401&md5=35aa1f8c068889a90254de41fc54602e" title="Click to view the MathML source">k=k+1mathContainer hidden">mathCode"><math altimg="si2.gif" overflow="scroll"><mi>kmi><mo>=mo><mi>kmi><mo>+mo><mn>1mn>math> holds) in the sense of Bloom and Ésik [2]. We apply these results to (1) obtain a generalization of Parikh's theorem, (2) compute the provenance of Datalog queries, and (3) analyze weighted pushdown systems. We further show how to compute Newton's method over any m>ωm>-continuous semiring by constructing a grammar unfolding w.r.t. “tree dimension”. We review several concepts equivalent to tree dimension and prove a new relation to pathwidth.