Logic in Computer Science (LICS 2001)

Paper: Perturbed Turing Machines and Hybrid Systems (at LICS 2001)

Authors: Eugene Asarin Ahmed Bouajjani

Abstract

We investigate the computational power of several models of dynamical systems under infinitesimal perturbations of their dynamics. We consider in our study models for discrete and continuous time dynamical systems: Turing machines, Piecewise affine maps, Linear hybrid automata and Piecewise constant derivative systems (a simple model of hybrid systems). We associate with each of these models a notion of perturbed dynamics by a small varepsilon (w.r.t. to a suitable metrics), and define the perturbed reachability relation as the intersection of all reachability relations obtained by varepsilon-perturbations, for all possible values of varepsilon. We show that for the four kinds of models we consider, the perturbed reachability relation is co-recursively enumerable, and that any co-r.e. relation can be defined as the perturbed reachability relation of such models. A corollary of this result is that systems that are robust, i.e., their reachability relation is stable under infinitesimal perturbation, are decidable.

BibTeX

  @InProceedings{AsarinBouajjani-PerturbedTuringMach,
    author = 	 {Eugene Asarin and Ahmed Bouajjani},
    title = 	 {Perturbed Turing Machines and Hybrid Systems},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {269--278},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }