The pseudo-Skolem Problem is decidable

Conference item

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

Authors: D'Costa, J; Karimov, T; Majumdar, R; Ouaknine, J; Salamati, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Host title: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
• Journal: LIPIcs
• Volume: 202
• Article number: 34
• Publication date: 2021-08-10
• Acceptance date: 2021-06-29
• Event title: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
• Event location: Tallinn, Estonia
• Event website: https://compose.ioc.ee/mfcs/
• Event start date: 2021-08-23
• Event end date: 2021-08-27
• DOI: 10.4230/LIPIcs.MFCS.2021.34
• EISSN: 1868-8969
• ISBN: 978-3-95977-201-3
• Language: English
• Keywords: linear dynamical systems; FFR; pseudo-orbits; orbit problem; Skolem problem