2026-07-21T20:02:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16838 2024-03-06T10:58:27Z ddc:004 open_access

The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems D'Costa, Julian Karimov, Toghrul Majumdar, Rupak Ouaknine, Joël Salamati, Mahmoud Worrell, James pseudo-orbits Orbit problem Skolem problem linear dynamical systems reachability We study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-reachability can be thought of as a robust version of classical reachability. Using an approach based on o-minimality of ℝ_exp we prove decidability of the discrete-time pseudo-reachability problem with arbitrary semialgebraic targets for diagonalisable linear dynamical systems. We also show that our method can be used to reduce the continuous-time pseudo-reachability problem to the (classical) time-bounded reachability problem, which is known to be conditionally decidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian D'Costa and Toghrul Karimov and Rupak Majumdar and Joël Ouaknine and Mahmoud Salamati and James Worrell 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.40 urn:nbn:de:0030-drops-168380 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.40 eng https://creativecommons.org/licenses/by/4.0/legalcode