## 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
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.

Imprint / Data Protection