Some bounds on the computational power of piecewise constant derivative systems
Identifieur interne : 001F71 ( Crin/Checkpoint ); précédent : 001F70; suivant : 001F72Some bounds on the computational power of piecewise constant derivative systems
Auteurs : Olivier BournezSource :
- Theory of computing systems ; 1999.
English descriptors
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 Σ_{d-2}-complete.
Links toward previous steps (curation, corpus...)
Links to Exploration step
CRIN:bournez99aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="239">Some bounds on the computational power of piecewise constant derivative systems</title></titleStmt><publicationStmt><idno type="RBID">CRIN:bournez99a</idno><date when="1999" year="1999">1999</date><idno type="wicri:Area/Crin/Corpus">002837</idno><idno type="wicri:Area/Crin/Curation">002837</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">002837</idno><idno type="wicri:Area/Crin/Checkpoint">001F71</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">001F71</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Some bounds on the computational power of piecewise constant derivative systems</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></author></analytic><series><title level="j">Theory of computing systems</title><imprint><date when="1999" type="published">1999</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>computability</term><term>dynamical system</term><term>real computational model</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2712">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 Σ_{d-2}-complete.</div></front></TEI><BibTex type="article"><ref>bournez99a</ref><crinnumber>99-R-409</crinnumber><category>1</category><equipe>PROTHEO</equipe><author><e>Bournez, Olivier</e></author><title>Some bounds on the computational power of piecewise constant derivative systems</title><journal>Theory of computing systems</journal><year>1999</year><volume>32</volume><number>1</number><pages>35-67</pages><month>{Jan-Feb}</month><keywords><e>real computational model</e><e>computability</e><e>dynamical system</e></keywords><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 Σ_{d-2}-complete.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001F71 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Checkpoint/biblio.hfd -nk 001F71 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Checkpoint
|type= RBID
|clé= CRIN:bournez99a
|texte= Some bounds on the computational power of piecewise constant derivative systems
}}
| This area was generated with Dilib version V0.6.33. |  |