Complexity bounds for zero-test algorithms
作者： Joris van der Hoeven , John Shackell
DOI: 10.1016/J.JSC.2006.06.001
关键词:
摘要: Abstract In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions first order differential equations with non-degenerate initial conditions. We will prove doubly exponential bound. This bound establishes analogue “witness conjectures”.
unirioja.es
core.ac.uk
kent.ac.uk
elsevier.com
texmacs.org 参考文章(19)
A Gabrielov, N Vorobjov, Complexity of computations with Pfaffian and Noetherian functions Springer. ,(2004)
Joris van der Hoeven, Transseries and Real Differential Algebra ,(2006)
Ariane Péladan-Germa, Testing Identities of Series Defined by Algebraic Partial Differential Equations Applicable Algebra in Engineering, Communication and Computing. pp. 393- 407 ,(1995) , 10.1007/3-540-60114-7_30
R. Loos, Generalized Polynomial Remainder Sequences Computing Supplementum. pp. 115- 137 ,(1982) , 10.1007/978-3-7091-3406-1_9
Alex J. Wilkie, Angus Macintyre, On the decidability of the real exponential field ,(1996)
John Shackell, Zero-equivalence in function fields defined by algebraic differential equations Transactions of the American Mathematical Society. ,vol. 336, pp. 151- 171 ,(1993) , 10.2307/2154342
Serge Lang, Transcendental numbers and diophantine approximations Bulletin of the American Mathematical Society. ,vol. 77, pp. 635- 677 ,(1971) , 10.1090/S0002-9904-1971-12761-1
B. Buchberger, G. E. Collins, R. Albrecht, R. Loos, Computer algebra: Symbolic and algebraic computation ,(1982)
Erwin H. Bareiss, Sylvester’s identity and multistep integer-preserving Gaussian elimination Mathematics of Computation. ,vol. 22, pp. 565- 578 ,(1968) , 10.1090/S0025-5718-1968-0226829-0
Bruno Salvy, John Shackell, Symbolic Asymptotics ,(2004)