Reachability in Dynamical Systems with Rounding

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

Beitragende

Abstract

We consider reachability in dynamical systems with discrete linear updates, but with fixed digital precision, i.e., such that values of the system are rounded at each step. Given a matrix M ∈ ℚ^{d × d}, an initial vector x ∈ ℚ^{d}, a granularity g ∈ ℚ_+ and a rounding operation [⋅] projecting a vector of ℚ^{d} onto another vector whose every entry is a multiple of g, we are interested in the behaviour of the orbit 𝒪 = ⟨[x], [M[x]],[M[M[x]]],… ⟩, i.e., the trajectory of a linear dynamical system in which the state is rounded after each step. For arbitrary rounding functions with bounded effect, we show that the complexity of deciding point-to-point reachability - whether a given target y ∈ ℚ^{d} belongs to 𝒪 - is PSPACE-complete for hyperbolic systems (when no eigenvalue of M has modulus one). We also establish decidability without any restrictions on eigenvalues for several natural classes of rounding functions.

Details

OriginalspracheEnglisch
Titel40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Redakteure/-innenNitin Saxena, Sunil Simon
Herausgeber (Verlag)Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Seiten36:1-36:17
ISBN (Print)978-3-95977-174-0
PublikationsstatusVeröffentlicht - 2020
Peer-Review-StatusNein

Publikationsreihe

Reihe40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) ; Vol. 182
Band182
ISSN1868-8969

Konferenz

Titel40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
KurztitelFSTTCS 2020
Veranstaltungsnummer
Dauer14 - 18 Dezember 2020
BekanntheitsgradInternationale Veranstaltung
Ortonline
StadtGoa
LandIndien

Externe IDs

Scopus 85101475898
ORCID /0000-0002-5321-9343/work/142236705

Schlagworte

Schlagwörter

  • Reachability in Dynamical Systems with Rounding, dynamical systems, rounding, reachability