## The Pseudo-Skolem Problem is decidable

*Julian D'Costa*, *Toghrul Karimov*, *Rupak Majumdar*,
*Joël
Ouaknine*, *Mahmoud Salamati*, *Sadegh Soudjani*,
and *James Worrell*
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,
surprisingly, the Skolem problem on pseudo-orbits is also
decidable. The former extends the seminal result of Kannan and Lipton
from orbits to pseudo-orbits. The latter is in contrast to the Skolem
problem for linear dynamical systems, which remains open for proper
orbits.

*Submitted*, 2021. 22 pages.

PDF
© 2021 Julian D'Costa, Toghrul Karimov, Rupak Majumdar,
Joël Ouaknine, Mahmoud Salamati, Sadegh Soudjani,
and James Worrell.

Imprint / Data Protection