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

DOI10.4230/LIPICS.FSCD.2019.7MaRDI QIDQ5089006zbMATH OpenFDO

Authors Maciej Bendkowski

Publication date 18 July 2022

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

zbMATH Keywords

combinatoricscomplexityexplicit substitutions\(\lambda\) calculus

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

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

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)