Geodesic
Algorithms yield upper bounds in differential algebra
Canadian journal of mathematics, Tome 75 (2023) no. 1, pp. 29-51

Voir la notice de l'article provenant de la source Cambridge

DOI

Consider an algorithm computing in a differential field with several commuting derivations such that the only operations it performs with the elements of the field are arithmetic operations, differentiation, and zero testing. We show that, if the algorithm is guaranteed to terminate on every input, then there is a computable upper bound for the size of the output of the algorithm in terms of the size of the input. We also generalize this to algorithms working with models of good enough theories (including, for example, difference fields).We then apply this to differential algebraic geometry to show that there exists a computable uniform upper bound for the number of components of any variety defined by a system of polynomial PDEs. We then use this bound to show the existence of a computable uniform upper bound for the elimination problem in systems of polynomial PDEs with delays.
DOI : 10.4153/S0008414X21000560
Mots-clés : delay PDEs, elimination of unknowns, uniform bounds, oracle machine 
Li, Wei; Ovchinnikov, Alexey; Pogudin, Gleb; Scanlon, Thomas. Algorithms yield upper bounds in differential algebra. Canadian journal of mathematics, Tome 75 (2023) no. 1, pp. 29-51. doi: 10.4153/S0008414X21000560
@article{10_4153_S0008414X21000560,
     author = {Li, Wei and Ovchinnikov, Alexey and Pogudin, Gleb and Scanlon, Thomas},
     title = {Algorithms yield upper bounds in differential algebra},
     journal = {Canadian journal of mathematics},
     pages = {29--51},
     year = {2023},
     volume = {75},
     number = {1},
     doi = {10.4153/S0008414X21000560},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008414X21000560/}
}
TY  - JOUR
AU  - Li, Wei
AU  - Ovchinnikov, Alexey
AU  - Pogudin, Gleb
AU  - Scanlon, Thomas
TI  - Algorithms yield upper bounds in differential algebra
JO  - Canadian journal of mathematics
PY  - 2023
SP  - 29
EP  - 51
VL  - 75
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008414X21000560/
DO  - 10.4153/S0008414X21000560
ID  - 10_4153_S0008414X21000560
ER  - 
%0 Journal Article
%A Li, Wei
%A Ovchinnikov, Alexey
%A Pogudin, Gleb
%A Scanlon, Thomas
%T Algorithms yield upper bounds in differential algebra
%J Canadian journal of mathematics
%D 2023
%P 29-51
%V 75
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008414X21000560/
%R 10.4153/S0008414X21000560
%F 10_4153_S0008414X21000560

Cité par Sources :