The Orbit Problem for Parametric Linear Dynamical Systems
share
We study a parametric version of the Kannan-Lipton Orbit Problem for linear dynamical systems. We show decidability in the case of one parameter and Skolem-hardness with four or more parameters. More precisely, consider M a d-dimensional square matrix whose entries are rational functions in one or more real variables. Given initial and target vectors u,v ∈ℚ^d, the parametrised point-to-point reachability problem asks whether there exist values of the parameters giving rise to a concrete matrix N ∈ℝ^d× d, and a positive integer n, such that N^n u = v. We show decidability in the case where M depends only upon a single parameter, and we exhibit a reduction from the well-known Skolem problem for linear recurrence sequences, indicating intractability in the case of four or more parameters.
READ FULL TEXT