The Pseudo-Reachability Problem for Linear Dynamical Systems

Joint work with Joel Ouaknine, James Worrell, Rupak Majumdar, Sadegh Soudjani, Julian D'Costa and Mahmoud Salamati. A linear dynamical system is given by an update matrix M and a starting point s. The reachability problem for LDS asks, given a semialgebraic target S, whether the orbit ever hits S. This problem is open and at least as hard as the Skolem and the Positivity problems for linear recurrence sequences. We consider reachability questions for pseudo-orbits, which is a fundamental notion in theory of dynamical systems going back to works of Anosov, Bowen and Conley. An epsilon-pseudo orbit of s under M is a sequence such that x_0=s and x_{n+1}=Mx_n + d_n for a perturbation d_n of size at most epsilon. The pseudo-reachability problem then is to determine if for every epsilon>0, there exists an epsilon-pseudo-orbit that hits S. This can be viewed as a robust version of the reachability problem. In our work presented at MFCS21, we showed that the pseudo-Skolem problem (pseudo-reachability problem where the target S is a hyperplane) is decidable using established methods. In our ongoing work, relying on o-minimality of R_exp, we have shown that for diagonalisable systems, the pseudo-reachability problem is decidable for arbitrary semialgebraic targets. Moreover, our methods can readily be applied in the continuous setting and to certain other formulations of the robust reachability problem.

Authors

• James Worrell

Keywords

No keywords are indexed for this paper.