(Optimal) duplication is not elementary recursive

DOI10.1016/J.IC.2004.05.001zbMath1075.68011OpenAlexW4213324284MaRDI QIDQ1881231

Simone Martini, Andrea Asperti, Paolo Coppola

Publication date: 4 October 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.05.001

zbMATH Keywords

elementary affine logicLamping's algorithm

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Combinatory logic and lambda calculus (03B40)

Related Items (4)

Light logics and optimal reduction: completeness and complexity ⋮ Is the Optimal Implementation Inefficient? Elementarily Not ⋮ On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy ⋮ Implicit computation complexity in higher-order programming languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• A simple proof of a theorem of Statman
• The typed lambda-calculus is not elementary recursive
• Light linear logic
• Parallel beta reduction is not elementary recursive
• Optimality and inefficiency
• On the dynamics of sharing graphs
• On global dynamics of optimal graph reduction
• Intuitionistic Light Affine Logic

This page was built for publication: (Optimal) duplication is not elementary recursive