论文标题
四舍五入的动态系统中的可达到性
Reachability in Dynamical Systems with Rounding
论文作者
论文摘要
我们考虑具有离散线性更新的动态系统中的可达到性，但是具有固定的数字精度，即，使系统值在每个步骤中都舍入。给定了一个矩阵$ m \ in \ mathbb {q}^{d \ times d} $，一个初始向量$ x \ in \ mathbb {q}^{d} $，一个粒度$ g \ in \ mathbb {q} $ \ MATHBB {q}^{d} $上的另一个向量的每个条目是$ g $的倍数，我们对轨道$ \ nathcal {o} = {o} = {<} [x]，[m [x]，[m [m [m [x]]，\ dots {\ dots {> dots inthord in thy thy thy tho tho tho thoytions的行为感兴趣。对于具有有界效果的任意舍入功能，我们表明确定点对点达到性的复杂性---给定的目标$ y \ in \ mathbb {q}^{d} $属于$ $ \ nathcal {o} $ ----- $ ----是pspace-pspace-pspace-pspace-pspote for ppspace compterte（何时没有$ m $ $ m $ $ modulus One）。我们还建立了可决定性，而无需对多种自然式圆形功能的特征值进行任何限制。
We consider reachability in dynamical systems with discrete linear updates, but with fixed digital precision, i.e., such that values of the system are rounded at each step. Given a matrix $M \in \mathbb{Q}^{d \times d}$, an initial vector $x\in\mathbb{Q}^{d}$, a granularity $g\in \mathbb{Q}_+$ and a rounding operation $[\cdot]$ projecting a vector of $\mathbb{Q}^{d}$ onto another vector whose every entry is a multiple of $g$, we are interested in the behaviour of the orbit $\mathcal{O}={<}[x], [M[x]],[M[M[x]]],\dots{>}$, i.e., the trajectory of a linear dynamical system in which the state is rounded after each step. For arbitrary rounding functions with bounded effect, we show that the complexity of deciding point-to-point reachability---whether a given target $y \in\mathbb{Q}^{d}$ belongs to $\mathcal{O}$---is PSPACE-complete for hyperbolic systems (when no eigenvalue of $M$ has modulus one). We also establish decidability without any restrictions on eigenvalues for several natural classes of rounding functions.
