scientific article; zbMATH DE number 512786

MaRDI QIDQ4281479zbMATH OpenFDO

Authors Daniel M. Leivant, Jean-Yves Marion

Publication date 10 March 1994

zbMATH Keywords

\(\lambda\)-representabilitycomputational complexity classespolytime functionstyped \(\lambda\)-calculiword algebra

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 445159
• Light types for polynomial time computation in lambda calculus
• Constant time parallel computations in \(\lambda\)-calculus
• Polynomial Time in the Parametric Lambda Calculus.

Cited in

(19)

• Light types for polynomial time computation in lambda calculus
• Word operation definable in the typed -calculus
• Functions over free algebras definable in the simply typed lambda calculus
• \textsc{ComplexityParser}: an automatic tool for certifying poly-time complexity of Java programs
• Realizability models for a linear dependent PCF
• An arithmetic for polynomial-time computation
• Higher-order interpretations and program complexity
• The role of polymorphism in the characterisation of complexity by soft types
• scientific article; zbMATH DE number 445159 (Why is no real title available?)
• A Short Introduction to Implicit Computational Complexity
• Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
• scientific article; zbMATH DE number 4180774 (Why is no real title available?)
• Parsimonious types and non-uniform computation
• scientific article; zbMATH DE number 1531370 (Why is no real title available?)
• Polynomial Time in the Parametric Lambda Calculus.
• The Safe Lambda Calculus
• A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations
• Towards the complexity analysis of programming language proof methods
• Typable fragments of polynomial automatic amortized resource analysis

This page was built for publication:

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