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