Some bounds on the computational power of piecewise constant derivative systems

Olivier Bournez 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the computational power of Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as computational machines working on a continuous space with a continuous time. We show that the computation time of these machines can be measured either as a discrete value, called discrete time, or as a continuous value, called continuous time. We relate the two notions of time for general PCD systems. We prove that general PCD systems are equivalent to Turing machines and linear machines in finite discrete time. We prove that the languages recognized by purely rational PCD systems in dimension $d$ in finite continuous time are precisely the languages of the $d-2^{th}$ level of the arithmetical hierarchy. Hence the reachability problem of purely rational PCD systems of dimension $d$ in finite continuous time is $\Sigma_{d-2}$-complete.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 1999, 32 (1), pp.35-67
Liste complète des métadonnées

https://hal.inria.fr/inria-00100817
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:51:32
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57

Identifiants

  • HAL Id : inria-00100817, version 1

Collections

Citation

Olivier Bournez. Some bounds on the computational power of piecewise constant derivative systems. Theory of Computing Systems, Springer Verlag, 1999, 32 (1), pp.35-67. 〈inria-00100817〉

Partager

Métriques

Consultations de la notice

112