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 λ-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.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01015171
Contributor : Hal Ifip <>
Submitted on : Thursday, November 24, 2016 - 10:50:02 AM
Last modification on : Tuesday, December 1, 2020 - 11:00:02 PM
Long-term archiving on: : Monday, March 20, 2017 - 4:49:50 PM

File

978-3-662-44602-7_13_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Patrick Baillot, Erika de Benedetti, Simona Ronchi Della Rocca. Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.151-163, ⟨10.1007/978-3-662-44602-7_13⟩. ⟨hal-01015171v2⟩

Share

Metrics

Record views

703

Files downloads

402