Hybrid automata, reachability, and Systems Biology

Hybrid automata are a powerful formalism for the representation of systems evolving according to both discrete and continuous laws. Unfortunately, undecidability soon emerges when one tries to automatically verify hybrid automata properties. An important verification problem is the reachability one that demands to decide whether a set of points is reachable from a starting region. If we focus on semi-algebraic hybrid automata the reachability problem is semi-decidable. However, high computational costs have to be afforded to solve it. We analyse this problem by exploiting some existing tools and we show that even simple examples cannot be efficiently solved. It is necessary to introduce approximations to reduce the number of variables, since this is the main source of runtime requirements. We propose some standard approximation methods based on Taylor polynomials and ad hoc strategies. We implement our methods within the software SAHA-Tool and we show their effectiveness on two biological examples: the Repressilator and the Delta-Notch protein signaling. © 2010 Elsevier B.V. All rights reserved.