The Orbit Problem for Parametric Linear Dynamical Systems

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragen

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.

Details

OriginalspracheEnglisch
Titel32nd International Conference on Concurrency Theory
Redakteure/-innenSerge Haddad, Daniele Varacca
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Seiten1-17
ISBN (elektronisch)9783959772037
ISBN (Print)978-3-95977-203-7
PublikationsstatusVeröffentlicht - 2021
Peer-Review-StatusNein

Publikationsreihe

Reihe32nd International Conference on Concurrency Theory (CONCUR 2021) ; Vol. 203
Band203
ISSN1868-8969

Konferenz

Titel32nd International Conference on Concurrency Theory
KurztitelCONCUR 2021
Dauer23 - 27 August 2021
Webseite
BekanntheitsgradInternationale Veranstaltung
Ortonline
StadtParis
LandFrankreich

Externe IDs

ORCID /0000-0002-5321-9343/work/142236686
Scopus 85115337111

Schlagworte

DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis

Schlagwörter

  • Orbit problem, linear dynamical systems, parametric