E. Asarin, O. Maler, A. Pnueli, On the Analysis of Dynamical Systems having Piecewise-Constant Derivatives.

In this paper we consider a class of hybrid systems, namely dynamical systems with piecewise-constant derivatives (PCD systems). Such systems consist of a partition of the Euclidean space into a finite set of polyhedral sets ({\it regions}). Within each region the dynamics is defined by a constant vector field, hence discrete transitions occur only on the boundaries between regions where the trajectories change their direction.
With respect to such systems we investigate the reachability question: {\it Given an effective description of the systems and of two polyhedral subsets $P$ and $Q$ of the state-space, is there a trajectory starting at some $\vx \in P$ and reaching some point in $Q$? } Our main results are a decision procedure for two-dimensional systems, and an undecidability result for three or more dimensions. [Postscript]