The Orbit Problem for Parametric Linear Dynamical Systems
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen
Beitragende
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 ∈ Qd, the parametric point-to-point orbit problem asks whether there exist values of the parameters giving rise to a concrete matrix N ∈ Rd×d, and a positive integer n ∈ N, such that N nu = 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.
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.
Details
Originalsprache | Englisch |
---|---|
Titel | 32nd International Conference on Concurrency Theory |
Redakteure/-innen | Serge Haddad, Daniele Varacca |
Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Seiten | 1-17 |
ISBN (elektronisch) | 9783959772037 |
ISBN (Print) | 978-3-95977-203-7 |
Publikationsstatus | Veröffentlicht - 2021 |
Peer-Review-Status | Nein |
Publikationsreihe
Reihe | 32nd International Conference on Concurrency Theory (CONCUR 2021) ; Vol. 203 |
---|---|
Band | 203 |
ISSN | 1868-8969 |
Konferenz
Titel | 32nd International Conference on Concurrency Theory |
---|---|
Kurztitel | CONCUR 2021 |
Dauer | 23 - 27 August 2021 |
Webseite | |
Bekanntheitsgrad | Internationale Veranstaltung |
Ort | online |
Stadt | Paris |
Land | Frankreich |
Externe IDs
ORCID | /0000-0002-5321-9343/work/142236686 |
---|---|
Scopus | 85115337111 |
Schlagworte
DFG-Fachsystematik nach Fachkollegium
Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis
ASJC Scopus Sachgebiete
Schlagwörter
- Orbit problem, linear dynamical systems, parametric