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 Rexp 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.
Proceedings of MFCS 22, LIPIcs 241, 2022. 19 pages.
PDF
© 2022 Julian D'Costa, Toghrul Karimov, Rupak Majumdar,
Joël Ouaknine, Mahmoud Salamati, and James Worrell.