Affordable Access

Publisher Website

Hybrid automata, reachability, and Systems Biology

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
411
Issue
20
Identifiers
DOI: 10.1016/j.tcs.2009.12.015
Keywords
  • Semi-Algebraic Automata
  • Reachability
  • Systems Biology
Disciplines
  • Biology
  • Computer Science
  • Mathematics

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.