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 - 1 Aug. 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, Linear dynamical systems, Parametric