conference paper
On recurrent reachability for continuous linear dynamical systems
published
yes
Ventsislav K
Chonev
author 36CBE2E6-F248-11E8-B48F-1D18A9856A87
Joël
Ouaknine
author
James
Worrell
author
KrCh
department
LICS: Logic in Computer Science
Quantitative Graph Games: Theory and Applications
project
Rigorous Systems Engineering
project
Quantitative Reactive Modeling
project
The continuous evolution of a wide variety of systems, including continous-time Markov chains and linear hybrid automata, can be
described in terms of linear differential equations. In this paper we study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target halfspace infinitely often. This recurrent reachability problem can
equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function f:R≥0 --> R satisfying a given linear
differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most 7, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.
IEEE2016New York, NY, USA
eng
LICS '1610.1145/2933575.2934548
515 - 524
Chonev, V. K., Ouaknine, J., & Worrell, J. (2016). On recurrent reachability for continuous linear dynamical systems. In <i>LICS ’16</i> (pp. 515–524). New York, NY, USA: IEEE. <a href="https://doi.org/10.1145/2933575.2934548">https://doi.org/10.1145/2933575.2934548</a>
Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” In <i>LICS ’16</i>, 515–24. IEEE, 2016. <a href="https://doi.org/10.1145/2933575.2934548">https://doi.org/10.1145/2933575.2934548</a>.
Chonev VK, Ouaknine J, Worrell J. On recurrent reachability for continuous linear dynamical systems. In: <i>LICS ’16</i>. IEEE; 2016:515-524. doi:<a href="https://doi.org/10.1145/2933575.2934548">10.1145/2933575.2934548</a>
V.K. Chonev, J. Ouaknine, J. Worrell, in:, LICS ’16, IEEE, 2016, pp. 515–524.
Chonev, Ventsislav K., et al. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” <i>LICS ’16</i>, IEEE, 2016, pp. 515–24, doi:<a href="https://doi.org/10.1145/2933575.2934548">10.1145/2933575.2934548</a>.
V. K. Chonev, J. Ouaknine, and J. Worrell, “On recurrent reachability for continuous linear dynamical systems,” in <i>LICS ’16</i>, New York, NY, USA, 2016, pp. 515–524.
Chonev VK, Ouaknine J, Worrell J. 2016. On recurrent reachability for continuous linear dynamical systems. LICS ’16. LICS: Logic in Computer Science 515–524.
13892018-12-11T11:51:44Z2020-08-11T10:09:09Z