Robust computations with dynamical systems

Olivier Bournez (1) , Daniel Graça (2) , Emmanuel Hainry (3)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 FCT - Faculdade de Ciências e Tecnologia [Faro]
3 CARTE - Theoretical adverse computations, and safety

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.

Mots clés: verification; model-checking; computable analysis; analog computation

Domaines: Autre [cs.OH]

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⟩