@inproceedings{c6f7f6c83b73497aabef9f713a684759,
title = "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 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 prove that the languages recognized by PCD systems in dimension d in finite continuous time are precisely the languages of the d — 2th 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].",
author = "Olivier Bournez",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 24th International Colloquium on Automata, Languages and Programming, ICALP 1997 ; Conference date: 07-07-1997 Through 11-07-1997",
year = "1997",
month = jan,
day = "1",
doi = "10.1007/3-540-63165-8\_172",
language = "English",
isbn = "3540631658",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "143--153",
editor = "Pierpaolo Degano and Roberto Gorrieri and Alberto Marchetti-Spaccamela",
booktitle = "Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings",
}