Reachability in Dynamical Systems with Rounding

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributed

Contributors

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

Original languageEnglish
Title of host publication40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
EditorsNitin Saxena, Sunil Simon
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages36:1-36:17
ISBN (print)978-3-95977-174-0
Publication statusPublished - 2020
Peer-reviewedNo

Publication series

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

Conference

Title40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Abbreviated titleFSTTCS 2020
Conference number
Duration14 - 18 December 2020
Degree of recognitionInternational event
Locationonline
CityGoa
CountryIndia

External IDs

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

Keywords

Keywords

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