Reachability in Dynamical Systems with Rounding
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed
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 language | English |
---|---|
Title of host publication | 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
Editors | Nitin Saxena, Sunil Simon |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 36:1-36:17 |
ISBN (print) | 978-3-95977-174-0 |
Publication status | Published - 2020 |
Peer-reviewed | No |
Publication series
Series | 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) ; Vol. 182 |
---|---|
Volume | 182 |
ISSN | 1868-8969 |
Conference
Title | 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
---|---|
Abbreviated title | FSTTCS 2020 |
Conference number | |
Duration | 14 - 18 December 2020 |
Degree of recognition | International event |
Location | online |
City | Goa |
Country | India |
External IDs
Scopus | 85101475898 |
---|---|
ORCID | /0000-0002-5321-9343/work/142236705 |
Keywords
Keywords
- Reachability in Dynamical Systems with Rounding, dynamical systems, rounding, reachability