Skip to Main content Skip to Navigation
New interface
Conference papers

Robust computations with dynamical systems

Abstract : In this paper we discuss the computational power of Lipschitz dynamical systems which are robust to infinitesimal perturbations. Whereas the study in [1] was done only for not-so-natural systems from a classical mathematical point of view (discontinuous differential equation systems, discontinuous piecewise affine maps, or perturbed Turing machines), we prove that the results presented there can be generalized to Lipschitz and computable dynamical systems. In other words, we prove that the perturbed reachability problem (i.e. the reachability problem for systems which are subjected to infinitesimal perturbations) is co-recursively enumerable for this kind of systems. Using this result we show that if robustness to infinitesimal perturbations is also required, the reachability problem becomes decidable. This result can be interpreted in the following manner: undecidability of verification doesn't hold for Lipschitz, computable and robust systems. We also show that the perturbed reachability problem is co-r.e. complete even for C ∞ -systems.
Document type :
Conference papers
Complete list of metadata
Contributor : Emmanuel Hainry Connect in order to contact the contributor
Submitted on : Wednesday, September 29, 2010 - 2:00:54 PM
Last modification on : Friday, May 13, 2022 - 10:18:05 PM
Long-term archiving on: : Thursday, October 25, 2012 - 4:16:23 PM


Files produced by the author(s)




Olivier Bournez, Daniel Graça, Emmanuel Hainry. Robust computations with dynamical systems. 35th international symposium on Mathematical Foundations of Computer Science - MFCS 2010, Aug 2010, Brno, Czech Republic. pp.198-208, ⟨10.1007/978-3-642-15155-2_19⟩. ⟨inria-00522029⟩



Record views


Files downloads