Implicit complexity in recursive analysis

Olivier Bournez 1 Walid Gomaa 2 Emmanuel Hainry 2, *
* Auteur correspondant
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Recursive analysis is a model of analog computation which is based on type 2 Turing machines. Various classes of functions computable in recursive analysis have recently been characterized in a machine independent and algebraical context. In particular nice connections between the class of computable functions (and some of its sub and sup-classes) over the reals and algebraically defined (sub- and sup-) classes of R-recursive functions à la Moore have been obtained. We provide in this paper a framework that allows to dive into complexity for functions over the reals. It indeed relates classical computability and complexity classes with the corresponding classes in recursive analysis. This framework opens the field of implicit complexity of functions over the reals. While our setting provides a new reading of some of the existing characterizations, it also provides new results: inspired by Bellantoni and Cook's characterization of polynomial time computable functions, we provide the first algebraic characterization of polynomial time computable functions over the reals.
Type de document :
Communication dans un congrès
Tenth International Workshop on Logic and Computational Complexity - LCC'09, Aug 2009, Los Angeles, United States. 2009
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00429964
Contributeur : Emmanuel Hainry <>
Soumis le : jeudi 5 novembre 2009 - 13:29:04
Dernière modification le : jeudi 10 mai 2018 - 02:06:41
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:28:45

Fichiers

lcc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00429964, version 1

Citation

Olivier Bournez, Walid Gomaa, Emmanuel Hainry. Implicit complexity in recursive analysis. Tenth International Workshop on Logic and Computational Complexity - LCC'09, Aug 2009, Los Angeles, United States. 2009. 〈inria-00429964〉

Partager

Métriques

Consultations de la notice

359

Téléchargements de fichiers

251