Decidable integration graphs

Integration graphs are a computational model developed in the attempt to id entify simple hybrid systems with decidable analysis problems. We start wit h the class of constant slope hybrid systems (CSHS), in which the right-han d side of all differential equations is an integer constant. We refer to co ntinuous variables whose right-hand side constants are always 1 as timers. All other continuous variables are called integrators, The first result sho wn in the paper is that simple questions such as reachability of a given st ate are undecidable for even this simple class of systems, To restrict the model even further, we impose the requirement that no test that refers to i ntegrators may appear within a loop in the graph. This restricted class of CSHS is called integration graphs. The main results of the paper are that t he reachability problem of integration graphs is decidable for two special cases: the case of a single timer and the case of a single test involving i ntegrators. The expressive power of the integration-graphs formalism is dem onstrated by showing that some typical problems studied within the context of the calculus of durations and timed statecharts can be formulated as rea chability problems for restricted integration graphs, and a high fraction o f these fall into the subclasses of a single timer or a single test involvi ng integrators. (C) 1999 Academic Press.