Parallel beta reduction is not elementary recursive

DOI10.1006/inco.2001.2869zbMath1005.68037OpenAlexW2007147248MaRDI QIDQ1854460

Andrea Asperti, Harry G. Mairson

Publication date: 14 January 2003

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

Full work available at URL: https://doi.org/10.1006/inco.2001.2869

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Functional programming and lambda calculus (68N18) Recursive functions and relations, subrecursive hierarchies (03D20) Combinatory logic and lambda calculus (03B40)

Related Items (9)

(Optimal) duplication is not elementary recursive ⋮ Coherence for sharing proof-nets ⋮ Light logics and optimal reduction: completeness and complexity ⋮ Linear dependent types in a call-by-value scenario ⋮ Strongly reducing variants of the Krivine abstract machine ⋮ The Useful MAM, a Reasonable Implementation of the Strong $$\lambda $$ -Calculus ⋮ A Fresh Look at the λ-Calculus ⋮ Is the Optimal Implementation Inefficient? Elementarily Not ⋮ Relating conflict-free stable transition and event models via redex families

Cites Work

• Paths, computations and labels in the \(\lambda\)-calculus
• The lambda calculus. Its syntax and semantics. Rev. ed.
• A simple proof of a theorem of Statman
• The typed lambda-calculus is not elementary recursive
• Optimality and inefficiency
• On global dynamics of optimal graph reduction
• The Calculi of Lambda Conversion. (AM-6)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parallel beta reduction is not elementary recursive