Skip to Main content Skip to Navigation
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 metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00429964
Contributor : Emmanuel Hainry <>
Submitted on : Thursday, November 5, 2009 - 1:29:04 PM
Last modification on : Thursday, March 5, 2020 - 6:21:46 PM
Long-term archiving on: : Thursday, June 17, 2010 - 7:28:45 PM

Files

lcc.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00429964, version 1

Collections

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

Share

Metrics

Record views

401

Files downloads

323