We study fundamental decision problems on linear dynamical systems in discrete time. We focus on pseudo-orbits, the collection of trajectories of the dynamical system for which there is an arbitrarily small perturbation at each step. Pseudo-orbits are generalizations of orbits in the topological theory of dynamical systems. We study the pseudo-orbit problem, whether a state belongs to the pseudo-orbit of another state, and the pseudo-Skolem problem, whether a hyperplane is reachable by an ε-pseudo-orbit for every ε. These problems are analogous to the well-studied orbit problem and Skolem problem on unperturbed dynamical systems. Our main results show that the pseudo-orbit problem is decidable in polynomial time and the Skolem problem on pseudo-orbits is decidable. The latter is in contrast to the Skolem problem for linear dynamical systems, which remains open for proper orbits.
Proceedings of MFCS 21, LIPIcs 202, 2021. 20 pages.
PDF
© 2021 Julian D'Costa, Toghrul Karimov, Rupak Majumdar,
Joël Ouaknine, Mahmoud Salamati, Sadegh Soudjani,
and James Worrell.