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.
Document type :
Reports
Complete list of metadatas

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
Long-term archiving on: Friday, November 25, 2016 - 11:51:59 AM

Identifiers

  • 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⟩

Share

Metrics

Record views

132

Files downloads

76