Reachability problems for hierarchical piecewise constant derivative systems

In this paper, we investigate the computability and complexity of reachability problems for two-dimensional hierarchical piecewise constant derivative (HPCD) systems. The main interest in HPCDs stems from the fact that their reachability problem is on the border between decidability and undecidability, since it is equivalent to that of reachability for one-dimensional piecewise affine maps (PAMs) which is a long standing open problem. Understanding the most expressive hybrid system models that retain decidability for reachability has generated a great deal of interest over the past few years. In this paper, we show a restriction of HPCDs (called RHPCDs) which leads to the reachability problem becoming decidable. We then study which additional powers we must add to the RHPCD model to render it 1D PAM-equivalent. Finally, we show NP-hardness of reachability for nondeterministic RHPCDs.