Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus

DOI10.1007/978-3-662-44602-7_13MaRDI QIDQ3190158zbMATH OpenOpenAlexFDO

Authors Patrick Baillot, Erika De Benedetti, Simona Ronchi Della Rocca

Publication date 15 September 2014

Published in Advanced Information Systems Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44602-7_13

zbMATH Keywords

implicit computational complexitylambda-calculuslinear logic

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• Polynomial Time in the Parametric Lambda Calculus.
• scientific article; zbMATH DE number 1342224
• Elementary explicit types and polynomial time operations
• Expressibility and Nonuniform Complexity Classes
• Characterizing complexity classes by higher type primitive recursive definitions
• scientific article; zbMATH DE number 4179364
• scientific article; zbMATH DE number 512786
• scientific article; zbMATH DE number 445159

Cited in

(9)

• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• Combining linear logic and size types for implicit complexity
• A type assignment for -calculus complete both for FPTIME and strong normalization
• Combining linear logic and size types for implicit complexity
• An elementary fragment of second-order lambda calculus
• Polynomial Time in the Parametric Lambda Calculus.
• New Computational Paradigms
• Polynomial and Exponential Bounded Logic Programs with Function Symbols: Some New Decidable Classes
• -symsym: an interactive tool for playing with involutions and types

This page was built for publication: Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3190158)