A natural counting of lambda terms

DOI10.1007/978-3-662-49192-8_15MaRDI QIDQ2794357zbMATH OpenOpenAlexFDO

Authors Maciej Bendkowski, Pierre Lescanne, Marek Zaionc, Katarzyna Grygiel

Publication date 10 March 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic densityblack-white treesfunctional programminglambda calculuszigzag-free trees

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18)

Abstract: We study the sequences of numbers corresponding to lambda terms of given sizes, where the size is this of lambda terms with de Bruijn indices in a very natural model where all the operators have size 1. For plain lambda terms, the sequence corresponds to two families of binary trees for which we exhibit bijections. We study also the distribution of normal forms, head normal forms and strongly normalizing terms. In particular we show that strongly normalizing terms are of density 0 among plain terms.

Recommendations

• Combinatorics of \(\lambda\)-terms: a natural approach
• On the number of lambda terms with prescribed size of their de Bruijn representation
• Enumerating lambda terms by weighted length of their de Bruijn representation
• On counting untyped lambda terms
• Counting and generating terms in the binary lambda calculus

Cited in

(22)

• Enumerating lambda terms by weighted length of their de Bruijn representation
• On the number of unary-binary tree-like structures with restrictions on the unary height
• On counting untyped lambda terms
• Statistical properties of lambda terms
• A note on discriminability of lambda terms
• Counting terms in the binary lambda calculus
• Lambda theories allowing terms with a finite number of fixed points
• Almost every simply typed -term has a long -reduction sequence
• A correspondence between rooted planar maps and normal planar lambda terms
• Ranking/unranking of lambda terms with compressed de Bruijn indices
• Enumeration of generalized BCI lambda-terms
• Combinatorics of \(\lambda\)-terms: a natural approach
• On the number of lambda terms with prescribed size of their de Bruijn representation
• Random generation of closed simply typed λ-terms: A synergy between logic programming and Boltzmann samplers
• scientific article; zbMATH DE number 7029315 (Why is no real title available?)
• Theoretical PearlsEnumerators of lambda terms are reducing
• scientific article; zbMATH DE number 845591 (Why is no real title available?)
• On the enumeration of closures and environments with an application to random generation
• Deriving efficient sequential and parallel generators for closed simply-typed lambda terms and normal forms
• On the number of variables in special classes of random lambda-terms
• Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels
• Normal-order reduction grammars

This page was built for publication: A natural counting of lambda terms

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