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.
https://hal.inria.fr/hal-01015171
Contributeur : Hal Ifip
<>
Soumis le : jeudi 24 novembre 2016 - 10:50:02
Dernière modification le : mardi 24 avril 2018 - 13:52:49
Document(s) archivé(s) le : lundi 20 mars 2017 - 16:49:50
