Non-uniform polytime computation in the infinitary affine lambda-calculus

DOI10.1007/978-3-662-43951-7_26MaRDI QIDQ5167847zbMATH OpenOpenAlexFDO

Authors Damiano Mazza

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Parsimonious types and non-uniform computation
• Polynomial Time in the Parametric Lambda Calculus.
• FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
• Non-linearity as the metric completion of linearity
• Foundations of Software Science and Computation Structures

Cited in

(12)

• Unary resolution: characterizing \textsc{Ptime}
• scientific article; zbMATH DE number 445159 (Why is no real title available?)
• Parsimonious types and non-uniform computation
• Church meets Cook and Levin
• FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
• Infinitary affine proofs
• Polynomial Time in the Parametric Lambda Calculus.
• Non-linearity as the metric completion of linearity
• Time-Complexity Semantics for Feasible Affine Recursions
• A syntactical analysis of non-size-increasing polynomial time computation
• Implicit computation complexity in higher-order programming languages
• Infinitary cut-elimination via finite approximations

This page was built for publication: Non-uniform polytime computation in the infinitary affine lambda-calculus

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