Some bounds on the computational power of piecewise constant derivative systems

Abstract. We study the computational power of Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems dened by a piecewise constant dierential equation and can be considered as computational machines working on a continuous space with a continu-ous time. We show that the computation time of these machines can be measured either as a discrete value, called discrete time, or as a continu-ous value, called continuous time. We prove that the languages recognized by PCD systems in dimension d in nite continuous time are precisely the languages of the d2th level of the arithmetical hierarchy. Hence we provide a precise characterization of the computational power of purely rational PCD systems in continuous time according to their dimension and we solve a problem left open by [2].