Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873826 | Information and Computation | 2018 | 23 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Patrick Baillot, Erika De Benedetti, Simona Ronchi Della Rocca,