Optimal semicomputable approximations to reachable and invariant sets
ACM Transactions on Computer Systems , Volume 41 - Issue 1 p. 33- 48
In this paper we consider the computation of reachable, viable and invariant sets for discrete-time systems. We use the framework of type-two effectivity, in which computations are performed by Turing machines with inﬁnite input and output tapes, with the representations of computable topology. We see that the reachable set is lower-semicomputable, and the viability and invariance kernels are upper-semicomputable. We then deﬁne an upper-semicomputable over-approximation to the reachable set, and lower-semicomputable under-approximations to the viability and invariance kernels, and show that these approximations are optimal.