Is the Optimal Implementation Inefficient? Elementarily Not

DOI10.4230/LIPICS.FSCD.2017.17zbMATH Open1434.68087OpenAlexW2759159410MaRDI QIDQ5111313FDOQ5111313

Marco Solieri, Stefano Guerrini

Publication date: 26 May 2020

Full work available at URL: https://hal.inria.fr/hal-01644123

Recommendations

• A general theory of sharing graphs
• Optimality and inefficiency: what isn't a cost model of the lambda calculus?
• Sharing implementations of graph rewriting systems
• scientific article; zbMATH DE number 1523048
• On the dynamics of sharing graphs

zbMATH Keywords

optimalitycomplexitylinear logic\(\lambda\)-calculussharing graphs

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05) Combinatory logic and lambda calculus (03B40) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Functional programming and lambda calculus (68N18)

Cites Work

• Title not available (Why is that?)
• The typed lambda-calculus is not elementary recursive
• Light linear logic
• On Constructor Rewrite Systems and the Lambda-Calculus
• Title not available (Why is that?)
• Intuitionistic Light Affine Logic
• Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine
• Context semantics, linear logic, and computational complexity
• Title not available (Why is that?)
• Coherence for sharing proof-nets
• Parallel beta reduction is not elementary recursive
• (Optimal) duplication is not elementary recursive
• Light logics and optimal reduction: completeness and complexity
• The bologna optimal higher-order machine
• Title not available (Why is that?)
• (Leftmost-outermost) beta reduction is invariant, indeed

Cited In (3)

• (In)efficiency and reasonable cost models
• Title not available (Why is that?)
• (Optimal) duplication is not elementary recursive

This page was built for publication: Is the Optimal Implementation Inefficient? Elementarily Not

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