Computation with perturbed dynamical systems

Abstract : This paper analyzes the computational power of dynamical systems robust to infinitesimal perturbations. Previous work on the subject has delved on very specific types of systems. Here we obtain results for broader classes of dynamical systems (including those systems defined by Lipschitz/analytic functions). In particular we show that systems robust to infinitesimal perturbations only recognize recursive languages. We also show the converse direction: every recursive language can be robustly recognized by a computable system. By other words we show that robustness is equivalent to decidability.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2013, 79 (5), pp.714-724. 〈10.1016/j.jcss.2013.01.025〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00643634
Contributeur : Emmanuel Hainry <>
Soumis le : lundi 2 février 2015 - 13:42:04
Dernière modification le : mercredi 25 avril 2018 - 10:45:21
Document(s) archivé(s) le : mercredi 27 mai 2015 - 15:41:15

Fichier

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

Identifiants

Collections

Citation

Olivier Bournez, Daniel Graça, Emmanuel Hainry. Computation with perturbed dynamical systems. Journal of Computer and System Sciences, Elsevier, 2013, 79 (5), pp.714-724. 〈10.1016/j.jcss.2013.01.025〉. 〈hal-00643634v2〉

Partager

Métriques

Consultations de la notice

622

Téléchargements de fichiers

187