mirage

Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy.

DSpace/Manakin Repository

Show simple item record

dc.contributor.author Laboratoire de l'informatique du parallélisme fr
dc.contributor.author Bournez, Olivier fr
dc.date.accessioned 2006-11-22T15:00:50Z
dc.date.available 2006-11-22T15:00:50Z
dc.date.issued 1997-05 en_US
dc.identifier.other LIP-RR - 1997-14 en_US
dc.identifier.uri http://hdl.handle.net/2332/671
dc.description.abstract (eng) We study the computational power of rational 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 prove that the languages recognized by rational PCD systems in dimension d=2k+3 (respectively: d=2k+4), k >= 0, in finite continuous time are precisely the languages of the omega ^k th (resp. omega ^k +1 th) level of the hyper-arithmetical hierarchy. Hence the reachability problem for rational PCD systems of dimension d=2k+3 (resp. d=2k+4), k >0 , is hyper-arithmetical and is Sigma_{omega ^k}-complete (resp. Sigma_{omega ^k +1}-complete). en_US
dc.description.abstract (fre) Nous étudions la puissance de calcul des systèmes à dérivée constante par morceaux (systèmes PCD) à coefficients rationnels. Les systèmes PCD sont des systèmes dynamiques définis par une équation différentielle constante par morceaux. Ils peuvent être vus comme des modèles de calcul évoluant sur espace continu avec un temps continu. Nous prouvons que les langages reconnus par des systèmes PCD rationnels en dimension d=2k+3 (respectivement: d=2k+4), k >= 0, en temps continu fini sont précisément les langages du omega ^k ieme (resp. omega ^k+1 ieme) niveau de la hiérarchie hyper-arithmétique. Ainsi le problème de l'atteignabilité des systèmes PCD de dimension d=2k+3 (resp. d=2k+4), k >0 , est hyper-arithmétique et est Sigma_{omega ^k}-complet (resp. Sigma_{omega ^k+1}-complet). fr
dc.format.extent 2+49p fr
dc.format.extent 525578 bytes
dc.format.extent 23 bytes
dc.format.mimetype application/pdf
dc.format.mimetype application/octet-stream
dc.language.iso eng en_US
dc.rights http://lara.inist.fr/utilisation.jsp en_US
dc.source.uri ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR1997/RR1997-14.ps.Z en_US
dc.subject Real Computability en_US
dc.subject Calculabilité réelle fr
dc.subject Continuous Time Computations en
dc.subject Dynamical Systems en
dc.subject Hyper-Arithmetical Hierarchy en
dc.subject Calculs en temps continu fr
dc.subject Hiérarchie hyper-arithmétique fr
dc.subject Systèmes dynamiques fr
dc.title Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy. en_US
dc.type Research report en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Bookmark and Share