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.
Additional Metadata
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)
Publisher CWI
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
Citation
Collins, P.J. (2008). Semantics and computability of the evolution of hybrid systems. Modelling, Analysis and Simulation [MAS]. CWI.