2026-07-23T07:16:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14474 2024-03-06T10:54:06Z ddc:004 open_access

The Pseudo-Skolem Problem is Decidable D'Costa, Julian Karimov, Toghrul Majumdar, Rupak Ouaknine, Joël Salamati, Mahmoud Soudjani, Sadegh Worrell, James Pseudo-orbits Orbit problem Skolem problem linear dynamical systems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian D'Costa and Toghrul Karimov and Rupak Majumdar and Joël Ouaknine and Mahmoud Salamati and Sadegh Soudjani and James Worrell 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.34 urn:nbn:de:0030-drops-144742 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.34 eng https://creativecommons.org/licenses/by/4.0/legalcode