License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.36
URN: urn:nbn:de:0030-drops-132778
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13277/
Go to the corresponding LIPIcs Volume Portal

Baier, Christel ; Funke, Florian ; Jantsch, Simon ; Karimov, Toghrul ; Lefaucheux, Engel ; Ouaknine, Joël ; Pouly, Amaury ; Purser, David ; Whiteland, Markus A.

Reachability in Dynamical Systems with Rounding

pdf-format:
LIPIcs-FSTTCS-2020-36.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{baier_et_al:LIPIcs:2020:13277,
  author =	{Christel Baier and Florian Funke and Simon Jantsch and Toghrul Karimov and Engel Lefaucheux and Jo{\"e}l Ouaknine and Amaury Pouly and David Purser and Markus A. Whiteland},
  title =	{{Reachability in Dynamical Systems with Rounding}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Nitin Saxena and Sunil Simon},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13277},
  URN =		{urn:nbn:de:0030-drops-132778},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.36},
  annote =	{Keywords: dynamical systems, rounding, reachability}
}

Keywords: dynamical systems, rounding, reachability
Collection: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI