Algorithms yield upper bounds in differential algebra
Algorithms yield upper bounds in differential algebra
复制标题
DOI：
10.4153/s0008414x21000560
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Wei Li;A. Ovchinnikov;G. Pogudin;T. Scanlon
中科院分区：
文献类型：
--
作者：
Wei Li;A. Ovchinnikov;G. Pogudin;T. Scanlon
考虑一个在微分域中计算的算法，该微分域中有几个可交换的导数，使得它对域中的元素执行的唯一操作是算术运算、微分和零测试。我们表明，如果该算法是保证终止于每个输入，那么有一个可计算的上限的大小的输出的算法的输入的大小。我们还将其推广到使用足够好的理论模型（包括，例如，差场）的算法。然后，我们将其应用到微分代数几何表明，存在一个可计算的统一上限的任何品种的组件定义的多项式偏微分方程系统的数量。然后，我们使用这个界显示存在一个可计算的统一上限的多项式偏微分方程系统中的消除问题的延迟。
Abstract 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.