Safe Recursion and Calculus over an Arbitrary Structure

Olivier Bournez 1 Paulin de Naurois 1 Jean-Yves Marion 2
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we show that the Bellantoni and Cook characterization of polynomial time computable functions in term of safe recursive functions can be transfered to the model of computation over an arbitrary structure developped by L. Blum, M. Shub and S. Smale. Hence, we provide an implicit complexity characterization of functions computable in polynomial time over any arbitrary structure.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/inria-00100884
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:52:41 PM
Last modification on : Thursday, January 11, 2018 - 6:19:57 AM

Identifiers

  • HAL Id : inria-00100884, version 1

Collections

Citation

Olivier Bournez, Paulin de Naurois, Jean-Yves Marion. Safe Recursion and Calculus over an Arbitrary Structure. Implicit Computational Complexity - ICC'2002, Jul 2002, Copenhagen, Denmark, 12 p. ⟨inria-00100884⟩

Share

Metrics

Record views

96