文章基本信息
- 标题：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
