Computability of finite-time reachable sets for hybrid systems
Pieter J. Collins, John Lygeros · 2006
In this paper we consider the computability of the evolution of hybrid systems, or equivalently, the computability of finite-time reachable sets. We use the framework of type-two computability theory and computable analysis, which gives a theory of computation for points, sets and maps by Turing machines, and is related to computable approximation. We show that, under suitable hypotheses, the system evolution may be lower or upper semicomputable, but cannot be both in the presence of grazing contact with the guard sets.