2026-08-05T04:55:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13277 2024-03-06T10:52:00Z ddc:004 open_access

Reachability in Dynamical Systems with Rounding Baier, Christel Funke, Florian Jantsch, Simon Karimov, Toghrul Lefaucheux, Engel Ouaknine, Joël Pouly, Amaury Purser, David Whiteland, Markus A. dynamical systems rounding reachability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christel Baier and Florian Funke and Simon Jantsch and Toghrul Karimov and Engel Lefaucheux and Joël Ouaknine and Amaury Pouly and David Purser and Markus A. Whiteland 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.36 urn:nbn:de:0030-drops-132778 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.36 eng https://creativecommons.org/licenses/by/3.0/legalcode