Skip to Main content Skip to Navigation
Conference papers

Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus

Abstract : In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k>=0, is given, by a type assignment system for a stratified lambda-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types. (This on-line version contains an appendix of 14 pages with full proofs of the statements)
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01015171
Contributor : Patrick Baillot <>
Submitted on : Wednesday, June 25, 2014 - 10:47:46 PM
Last modification on : Monday, March 29, 2021 - 2:46:57 PM
Long-term archiving on: : Thursday, September 25, 2014 - 11:49:09 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01015171, version 1

Citation

Patrick Baillot, Erika de Benedetti, Simona Ronchi Della Rocca. Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus. IFIP conference on Theoretical Computer Science, Aug 2014, Rome, Italy. 15 p. ⟨hal-01015171v1⟩

Share

Metrics

Record views

235

Files downloads

249