文章基本信息

标题：Reachability in Dynamical Systems with Rounding
本地全文：下载
作者：Christel Baier ; Florian Funke ; Simon Jantsch 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-17
DOI：10.4230/LIPIcs.FSTTCS.2020.36
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 â^^ â"S^{d Ã- d}, an initial vector x â^^ â"S^{d}, a granularity g â^^ â"S_ and a rounding operation [â<.] projecting a vector of â"S^{d} onto another vector whose every entry is a multiple of g, we are interested in the behaviour of the orbit ð'ª = âY¨[x], [M[x]],[M[M[x]]],â¦ âY©, 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 â^^ â"S^{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.
关键词：dynamical systems; rounding; reachability