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.
Type de document :
Communication dans un congrès
Petr Hlineny and Antonin Kucera. 35th international symposium on Mathematical Foundations of Computer Science - MFCS 2010, Aug 2010, Brno, Czech Republic. Springer-Verlag, 6281, pp.198-208, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15155-2_19〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00522029
Contributeur : Emmanuel Hainry <>
Soumis le : mercredi 29 septembre 2010 - 14:00:54
Dernière modification le : jeudi 10 mai 2018 - 02:06:51
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 16:16:23

Fichier

mfcs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Olivier Bournez, Daniel Graça, Emmanuel Hainry. Robust computations with dynamical systems. Petr Hlineny and Antonin Kucera. 35th international symposium on Mathematical Foundations of Computer Science - MFCS 2010, Aug 2010, Brno, Czech Republic. Springer-Verlag, 6281, pp.198-208, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15155-2_19〉. 〈inria-00522029〉

Partager

Métriques

Consultations de la notice

307

Téléchargements de fichiers

117