Characterizing polynomial and exponential complexity classes in elementary lambda-calculus

In this paper an implicit characterization of the complexity classes kEXP and kFEXP, 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)...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2018-06, Vol.248, p.55-77
Main Authors: Baillot, Patrick, de Benedetti, Erika, Ronchi Della Rocca, Simona
Format: Article
Language:English
Subjects:
Computer Science
Logic in Computer Science
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper an implicit characterization of the complexity classes kEXP and kFEXP, 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 kEXP is characterized by a hierarchy of types.
ISSN:0890-5401
1090-2651