The Orbit Problem for 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 m...
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Dagstuhl Research Online Publication Server
2021
|
| _version_ | 1797068784595369984 |
|---|---|
| author | Baier, C Jantsch, S Lefaucheux, E Ouaknine, J Whiteland, MA Funke, F Karimov, T Luca, F Purser, D Worrell, J |
| author_facet | Baier, C Jantsch, S Lefaucheux, E Ouaknine, J Whiteland, MA Funke, F Karimov, T Luca, F Purser, D Worrell, J |
| author_sort | Baier, C |
| collection | OXFORD |
| description | 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.
|
| first_indexed | 2024-03-06T22:15:06Z |
| format | Conference item |
| id | oxford-uuid:5320ba64-e6a7-4bfa-b1a2-ac814c2a3628 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:15:06Z |
| publishDate | 2021 |
| publisher | Dagstuhl Research Online Publication Server |
| record_format | dspace |
| spelling | oxford-uuid:5320ba64-e6a7-4bfa-b1a2-ac814c2a36282022-03-26T16:29:40ZThe Orbit Problem for parametric linear dynamical systemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:5320ba64-e6a7-4bfa-b1a2-ac814c2a3628EnglishSymplectic ElementsDagstuhl Research Online Publication Server2021Baier, CJantsch, SLefaucheux, EOuaknine, JWhiteland, MAFunke, FKarimov, TLuca, FPurser, DWorrell, JWe 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. |
| spellingShingle | Baier, C Jantsch, S Lefaucheux, E Ouaknine, J Whiteland, MA Funke, F Karimov, T Luca, F Purser, D Worrell, J The Orbit Problem for parametric linear dynamical systems |
| title | The Orbit Problem for parametric linear dynamical systems |
| title_full | The Orbit Problem for parametric linear dynamical systems |
| title_fullStr | The Orbit Problem for parametric linear dynamical systems |
| title_full_unstemmed | The Orbit Problem for parametric linear dynamical systems |
| title_short | The Orbit Problem for parametric linear dynamical systems |
| title_sort | orbit problem for parametric linear dynamical systems |
| work_keys_str_mv | AT baierc theorbitproblemforparametriclineardynamicalsystems AT jantschs theorbitproblemforparametriclineardynamicalsystems AT lefaucheuxe theorbitproblemforparametriclineardynamicalsystems AT ouakninej theorbitproblemforparametriclineardynamicalsystems AT whitelandma theorbitproblemforparametriclineardynamicalsystems AT funkef theorbitproblemforparametriclineardynamicalsystems AT karimovt theorbitproblemforparametriclineardynamicalsystems AT lucaf theorbitproblemforparametriclineardynamicalsystems AT purserd theorbitproblemforparametriclineardynamicalsystems AT worrellj theorbitproblemforparametriclineardynamicalsystems AT baierc orbitproblemforparametriclineardynamicalsystems AT jantschs orbitproblemforparametriclineardynamicalsystems AT lefaucheuxe orbitproblemforparametriclineardynamicalsystems AT ouakninej orbitproblemforparametriclineardynamicalsystems AT whitelandma orbitproblemforparametriclineardynamicalsystems AT funkef orbitproblemforparametriclineardynamicalsystems AT karimovt orbitproblemforparametriclineardynamicalsystems AT lucaf orbitproblemforparametriclineardynamicalsystems AT purserd orbitproblemforparametriclineardynamicalsystems AT worrellj orbitproblemforparametriclineardynamicalsystems |