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.
Type de document :
Communication dans un congrès
Implicit Computational Complexity - ICC'2002, Jul 2002, Copenhagen, Denmark, 12 p, 2002
Liste complète des métadonnées

https://hal.inria.fr/inria-00100884
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:52:41
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57

Identifiants

  • 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, 2002. 〈inria-00100884〉

Partager

Métriques

Consultations de la notice

83