# Characterising Polytime through higher type Recursion

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.
Keywords :
Document type :
Reports
Domain :

https://hal.inria.fr/inria-00098738
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:22:05 AM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM
Document(s) archivé(s) le : Friday, November 25, 2016 - 11:51:59 AM

### Identifiers

• HAL Id : inria-00098738, version 1

### Citation

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

Record views