Characterising Polytime through higher type Recursion

Karl-Heinz Niggl 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : It is shown how to restrict recursion on notation in all finite types so as to characterise the polynomial time computable functions. The restrictions are obtained by enriching the type structure with the formation of types $!\sigma$, and by adding linear concepts to the lambda calculus.
Type de document :
Rapport
[Intern report] 98-R-239 || niggl98a, 1998, 17 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00098738
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:22:05
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 11:51:59

Fichiers

Identifiants

  • HAL Id : inria-00098738, version 1

Collections

Citation

Karl-Heinz Niggl. Characterising Polytime through higher type Recursion. [Intern report] 98-R-239 || niggl98a, 1998, 17 p. 〈inria-00098738〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

42