Skip to Main content Skip to Navigation
New interface
Conference papers

Implicit complexity in recursive analysis

Olivier Bournez 1 Walid Gomaa 2 Emmanuel Hainry 2, * 
* Corresponding author
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Emmanuel Hainry Connect in order to contact the contributor
Submitted on : Thursday, November 5, 2009 - 1:29:04 PM
Last modification on : Friday, May 13, 2022 - 10:18:05 PM
Long-term archiving on: : Thursday, June 17, 2010 - 7:28:45 PM


Files produced by the author(s)


  • HAL Id : inria-00429964, version 1



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. ⟨inria-00429964⟩



Record views


Files downloads