Towards the average-case analysis of substitution resolution in -calculus

DOI10.4230/LIPICS.FSCD.2019.7MaRDI QIDQ5089006FDOQ5089006

Authors: Maciej Bendkowski 

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1812.04452

Recommendations

• Statistical properties of lambda terms
• λν, a calculus of explicit substitutions which preserves strong normalisation
• Strong normalization of substitutions
• On randomised strategies in the \(\lambda \)-calculus
• scientific article; zbMATH DE number 1722651

zbMATH Keywords

combinatoricscomplexityexplicit substitutions\(\lambda\) calculus

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Cites Work

• Analytic combinatorics
• Singularity Analysis of Generating Functions
• Complexity analysis of term-rewriting systems
• A Machine-Oriented Logic Based on the Resolution Principle
• Title not available (Why is that?)
• Explicit substitutions
• Optimality and inefficiency: what isn't a cost model of the lambda calculus?
• λν, a calculus of explicit substitutions which preserves strong normalisation
• Title not available (Why is that?)
• Normal-order reduction grammars
• Downward Löwenheim-Skolem theorem and interpolation in logics with constructors
• (Leftmost-outermost) beta reduction is invariant, indeed
• Almost every simply typed \(\lambda\)-term has a long \(\beta\)-reduction sequence
• On the likelihood of normalization in combinatory logic

Cited In (1)

• Towards the average-case analysis of substitution resolution in $\lambda$-calculus

This page was built for publication: Towards the average-case analysis of substitution resolution in \(\lambda\)-calculus

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