The Orbit Problem for Parametric Linear Dynamical Systems

Christel BaierChristel Baier, Florian FunkeFlorian Funke, Simon JantschSimon Jantsch, Toghrul KarimovToghrul Karimov, Engel LefaucheuxEngel Lefaucheux, Florian LucaFlorian Luca, Joël OuaknineJoël Ouaknine, David PurserDavid Purser, Markus A. WhitelandMarkus A. Whiteland, James WorrellJames Worrell

DOI Link

Christel Baier, Florian Funke, Simon Jantsch, Toghrul Karimov, Engel Lefaucheux, Florian Luca, Joël Ouaknine, David Purser, Markus A. Whiteland, James Worrell
The Orbit Problem for Parametric Linear Dynamical Systems
In Haddad, Serge and Varacca, Daniele, eds., 32nd International Conference on Concurrency Theory, CONCUR, volume 203 of LIPIcs, 28:1--28:17, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Details
Bibtex

KurzfassungAbstract
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∈Qd, 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.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{BFJKLLOPWW2021,
  author    = {Christel Baier and Florian Funke and Simon Jantsch and Toghrul
               Karimov and Engel Lefaucheux and Florian Luca and Jo{\"{e}}l
               Ouaknine and David Purser and Markus A. Whiteland and James
               Worrell},
  title     = {The Orbit Problem for Parametric Linear Dynamical Systems},
  editor    = {Haddad and Serge and Varacca and Daniele},
  booktitle = {32nd International Conference on Concurrency Theory, {CONCUR}},
  series    = {LIPIcs},
  volume    = {203},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2021},
  pages     = {28:1--28:17},
  doi       = {10.4230/LIPIcs.CONCUR.2021.28}
}