A computable and compositional semantics for hybrid automata

Hybrid Systems are systems having a mixed discrete and continu- ous behaviour that cannot be characterized faithfully using either only discrete or only continuous models. A good framework for hybrid systems should support their compositional description and analysis, since commonly systems are specified by a composition of smaller subsystems, to cope with the complexity of their monolithic representation. Moreover, since the reachability problem for hybrid systems is undecidable, one should investigate the conditions that guarantee approximate computability of composition, when only approximations to the exact problem data are available. In this paper, we propose an automata-based formalism (HIOA) for hybrid systems that is compositional and for which the evolu- tion can be computed approximately. The main results are that the composition of compatible HIOA yields a pre-HIOA; a dominance result on the composition of HIOA by which we can replace any component in a composition by another one that exhibits the same external behaviour without affecting the behaviour of the composi- tion; finally, the key result that the composition of two compatible upper(lower)-semicontinuous HIOA is a computable upper(lower)- semicontinuous pre-HIOA, which entails that the evolution of the composition is upper(lower)-semicomputable. A discussion on how compositionality/computability are handled in state-of-art libraries for reachability analysis closes the paper.