2026-08-10T23:44:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14405 2024-03-12T12:00:11Z ddc:004 open_access

The Orbit Problem for Parametric Linear Dynamical Systems Baier, Christel Funke, Florian Jantsch, Simon Karimov, Toghrul Lefaucheux, Engel Luca, Florian Ouaknine, Joël Purser, David Whiteland, Markus A. Worrell, James Orbit problem parametric linear dynamical systems 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 ∈ ℚ^d, the parametric point-to-point orbit 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christel Baier and Florian Funke and Simon Jantsch and Toghrul Karimov and Engel Lefaucheux and Florian Luca and Joël Ouaknine and David Purser and Markus A. Whiteland and James Worrell 2021 Is Part Of LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2021.28 urn:nbn:de:0030-drops-144053 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.28 eng https://creativecommons.org/licenses/by/4.0/legalcode