The Orbit Problem for parametric linear dynamical systems

Christel Baier, Florian Funke, Simon Jantsch, Engel Lefaucheux, Florian Luca, Joël Ouaknine, David Purser, Markus A. Whiteland, and James Worrell

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 two or more parameters.

More precisely, consider a d-dimensional square matrix M whose entries are algebraic functions in one or more real variables. Given initial and target vectors uv ∈ Qd, the parametric point-to-point orbit problem asks whether there exist values of the parameters giving rise to a concrete matrix N ∈ Rd×d, and a positive integer n ∈ N, such that Nnu = v.

We show decidability for the case in which M depends only upon a single parameter, and we exhibit a reduction from the well-known Skolem problem for linear recurrence sequences, suggesting intractability in the case of two or more parameters.

Proceedings of CONCUR 21, LIPIcs 203, 2021. 18 pages.

PDF © 2021 Christel Baier, Florian Funke, Simon Jantsch, Engel Lefaucheux, Florian Luca, Joël Ouaknine, David Purser, Markus A. Whiteland, and James Worrell.



Imprint / Data Protection