FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness

DOI10.1017/S0956796804005131zbMath1063.68036OpenAlexW207336988MaRDI QIDQ4660260

Harry G. Mairson

Publication date: 21 March 2005

Published in: Journal of Functional Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0956796804005131

zbMATH Keywords

Church's coding of Booleans

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Combinatory logic and lambda calculus (03B40)

Related Items (6)

A type-assignment of linear erasure and duplication ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Unnamed Item ⋮ Linear lambda terms as invariants of rooted trivalent maps ⋮ Linear Lambda Calculus and Deep Inference ⋮ Implicit computation complexity in higher-order programming languages

This page was built for publication: FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness