Semantics and computability of the evolution of hybrid systems
In this paper we consider the semantics for the evolution of hybrid systems, and the computability of the evolution with respect to these semantics. We show that with respect to lower semantics, the finite-time reachable sets are lower-semicomputable, and with respect to upper semantics, the finite-time reachable sets are upper-semicomputable. We use the framework of type-two Turing computability theory and computable analysis, which deal with obtaining approximation results with guaranteed error bounds from approximate data. We show that in general, we cannot find a semantics for which the evolution is both lower- and upper- semicomputable, unless the system is free from tangential and corner contact with the guard sets. We highlight the main points of the theory with simple examples illustrating the subtleties involved.
|Keywords||Computable analysis, hybrid system, reachable set|
|MSC||Attainable sets (msc 93B03), Explicit machine computation and programs (not the theory of computation or programming) (msc 93-04), Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (msc 68Q17), Computational methods (msc 93B40)|
|THEME||Life Sciences (theme 5), Energy (theme 4)|
|Series||Modelling, Analysis and Simulation [MAS]|
|Project||Computational Topology for Systems and Control|
|Note||This research was supported by Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO) Vidi grant 639.032.408|
Collins, P.J. (2008). Semantics and computability of the evolution of hybrid systems. Modelling, Analysis and Simulation [MAS]. CWI.