Conference item
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.
- Publication status:
- Published
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 790.9KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.CONCUR.2021.28
Authors
- Publisher:
- Dagstuhl Research Online Publication Server
- Journal:
- Leibniz International Proceedings in Informatics More from this journal
- Volume:
- 203
- Pages:
- 28:1-28:17
- Publication date:
- 2021-08-13
- Event title:
- 32nd International Conference on Concurrency Theory (CONCUR 2021)
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959772037
- Language:
-
English
- Keywords:
- Pubs id:
-
1195981
- Local pid:
-
pubs:1195981
- Deposit date:
-
2021-10-11
Terms of use
- Copyright holder:
- Baier et al.
- Copyright date:
- 2021
- Rights statement:
- © Christel Baier, Florian Funke, Simon Jantsch, Toghrul Karimov, Engel Lefaucheux, Florian Luca, Joël Ouaknine, David Purser, Markus A.Whiteland, and James Worrell; licensed under Creative Commons License CC-BY 4.0.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record