论文标题
在紧凑的半格式集上界定线性动力学系统的逃生时间
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
论文作者
论文摘要
我们研究了紧凑的半格式集合的离散时间线性动力学系统的逃生问题。我们建立了一个均匀的上限，该界限是在为逃脱有理数据定义的紧凑型半ge体集所需的每个轨道所需的迭代次数。我们的界限在环境维度中是双重指数的，在用于定义半格式集合的多项式的程度上单独指数，并在这些多项式的系数和矩阵杂物的粘液质量中单独指数。我们证明，通过提供匹配的下边界，我们的界限很紧。
We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly exponential in the ambient dimension, singly exponential in the degrees of the polynomials used to define the semialgebraic set, and singly exponential in the bitsize of the coefficients of these polynomials and the bitsize of the matrix entries. We show that our bound is tight by providing a matching lower bound.
