On recurrent reachability for continuous linear dynamical systems

DOI10.1145/2933575.2934548MaRDI QIDQ4635910zbMATH OpenOpenAlexFDO

Authors Ventsislav Chonev, Joël Ouaknine, James Worrell

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.03632

zbMATH Keywords

differential equationsDiophantine approximationlinear dynamical systemsreachabilitySkolem problem

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Linear ordinary differential equations and systems (34A30)

Abstract: The continuous evolution of a wide variety of systems, including continuous-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 $$ of a system of linear differential equations $$ 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:mathbb{R}_{geq0}ightarrowmathbbR$ 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.

Recommendations

• On the Skolem problem for continuous linear dynamical systems
• Reachability in Linear Dynamical Systems
• The continuous Skolem-Pisot problem
• scientific article; zbMATH DE number 1574496
• scientific article; zbMATH DE number 7559115

Cited in

(12)

• Reachability analysis of linear dynamic systems with constant, arbitrary, and Lipschitz continuous inputs
• Exact solutions in log-concave maximum likelihood estimation
• scientific article; zbMATH DE number 1574496 (Why is no real title available?)
• Reachability in Linear Dynamical Systems
• scientific article; zbMATH DE number 123744 (Why is no real title available?)
• On the Skolem problem for continuous linear dynamical systems
• A Survey on Analog Models of Computation
• On the polytope escape problem for continuous linear dynamical systems
• On the complexity of robust eventual inequality testing for C-finite functions
• Invariants for continuous linear dynamical systems
• Axiomatization of compact initial value problems: open properties
• The continuous Skolem-Pisot problem

This page was built for publication: On recurrent reachability for continuous linear dynamical systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635910)