| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 193.86 KB | Adobe PDF |
Advisor(s)
Abstract(s)
In this paper we discuss the computational power of Lipschitz
dynamical systems which are robust to in nitesimal perturbations.
Whereas the study in [1] was done only for not-so-natural systems from
a classical mathematical point of view (discontinuous di erential equation
systems, discontinuous piecewise a ne 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 in nitesimal perturbations)
is co-recursively enumerable for this kind of systems. Using
this result we show that if robustness to in nitesimal perturbations is
also required, the reachability problem becomes decidable. This result
can be interpreted in the following manner: undecidability of veri cation
doesn't hold for Lipschitz, computable and robust systems.
We also show that the perturbed reachability problem is co-r.e. complete
even for C1-systems.
Description
Keywords
Veri cation Analog computations Computable analysis Model-checking