License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2021.28
URN: urn:nbn:de:0030-drops-144053
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14405/
Baier, Christel ;
Funke, Florian ;
Jantsch, Simon ;
Karimov, Toghrul ;
Lefaucheux, Engel ;
Luca, Florian ;
Ouaknine, Joël ;
Purser, David ;
Whiteland, Markus A. ;
Worrell, James
The Orbit Problem for Parametric Linear Dynamical Systems
Abstract
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.
BibTeX - Entry
@InProceedings{baier_et_al:LIPIcs.CONCUR.2021.28,
author = {Baier, Christel and Funke, Florian and Jantsch, Simon and Karimov, Toghrul and Lefaucheux, Engel and Luca, Florian and Ouaknine, Jo\"{e}l and Purser, David and Whiteland, Markus A. and Worrell, James},
title = {{The Orbit Problem for Parametric Linear Dynamical Systems}},
booktitle = {32nd International Conference on Concurrency Theory (CONCUR 2021)},
pages = {28:1--28:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-203-7},
ISSN = {1868-8969},
year = {2021},
volume = {203},
editor = {Haddad, Serge and Varacca, Daniele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14405},
URN = {urn:nbn:de:0030-drops-144053},
doi = {10.4230/LIPIcs.CONCUR.2021.28},
annote = {Keywords: Orbit problem, parametric, linear dynamical systems}
}
Keywords: |
|
Orbit problem, parametric, linear dynamical systems |
Collection: |
|
32nd International Conference on Concurrency Theory (CONCUR 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
13.08.2021 |