## The Orbit Problem for parametric linear dynamical systems

*Christel Baier*, *Florian Funke*,
*Simon Jantsch*,
*Toghrul Karimov*,
*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
*u*, *v* ∈ **Q**^{d}, the
parametric point-to-point orbit problem asks whether there exist
values of the parameters giving rise to a concrete matrix
*N* ∈ **R**^{d×d},
and a positive integer *n* ∈ **N**, such
that *N*^{n}*u* = *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, Toghrul Karimov, Engel
Lefaucheux, Florian Luca, Joël Ouaknine, David Purser,
Markus A. Whiteland, and James Worrell.

Imprint / Data Protection