Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-00643634
Contributor : Emmanuel Hainry <>
Submitted on : Monday, February 2, 2015 - 1:42:04 PM
Last modification on : Thursday, March 5, 2020 - 6:24:12 PM
Long-term archiving on: : Wednesday, May 27, 2015 - 3:41:15 PM

File

jcss13.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

887

Files downloads

689