3531 articles – 5253 Notices  [english version]

hal-00643634, version 1

Computation with perturbed dynamical systems

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

(13/05/2011)

Résumé : 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.

  • a –  Universidade do Algarve
  • b –  Université de Lorraine
  • 1 :  Laboratoire d'informatique de l'école polytechnique (LIX)
  • CNRS : UMR7161 – Polytechnique - X
  • 2 :  Faculdade de Ciências e Tecnologia (FCT)
  • Universidade do Algarve
  • 3 :  CARTE (INRIA Nancy - Grand Est / LORIA)
  • CNRS : UMR7503 – INRIA – Université de Lorraine
  • Domaine : Informatique/Autre
  • Mots-clés : Dynamical systems – reachability – robustness – computational power – verification
  • Commentaire : Soumis
 
  • hal-00643634, version 1
  • http://hal.inria.fr/hal-00643634
  • oai:hal.inria.fr:hal-00643634
  • Contributeur : Emmanuel Hainry <>
  • Soumis le : Mardi 22 Novembre 2011, 14:33:56
  • Dernière modification le : Mardi 27 Novembre 2012, 14:56:54