Counting and generating terms in the binary lambda calculus

DOI10.1017/S0956796815000271zbMath1419.68039arXiv1511.05334MaRDI QIDQ5371959

Pierre Lescanne, Katarzyna Grygiel

Publication date: 23 October 2017

Published in: Journal of Functional Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Functional programming and lambda calculus (68N18) Combinatory logic and lambda calculus (03B40)

Related Items (8)

Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels ⋮ On the enumeration of closures and environments with an application to random generation ⋮ Unnamed Item ⋮ On some enumerative problems in lambda calculus ⋮ Enumerating lambda terms by weighted length of their de Bruijn representation ⋮ Normal-order reduction grammars ⋮ Deriving Efficient Sequential and Parallel Generators for Closed Simply-Typed Lambda Terms and Normal Forms ⋮ Statistical properties of lambda terms

Uses Software

• Haskell

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotics and random sampling for BCI and BCK lambda terms
• Enumeration of generalized BCI lambda-terms
• On counting untyped lambda terms
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Asymptotically almost all \lambda-terms are strongly normalizing
• Boltzmann Sampling of Unlabelled Structures
• Lambda terms of bounded unary height
• Counting and generating lambda terms
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Counting and generating terms in the binary lambda calculus