On counting untyped lambda terms

Pierre Lescanne (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We present several results on counting untyped lambda terms, i.e., on telling how many terms belong to such or such class, according to the size of the terms and/or to the number of free variables.

Keywords: Complexity; Enumeration; Expected complexity; Lambda calculus complexity enumeration expected complexity

Domains: Computer Science [cs]; Data Structures and Algorithms [cs.DS]; Computer Science [cs]; Logic in Computer Science [cs.LO]; Computer Science [cs]; Discrete Mathematics [cs.DM]; Mathematics [math]; Combinatorics [math.CO]

Pierre Lescanne. On counting untyped lambda terms. Theoretical Computer Science, 2013, 474, pp.80-97. ⟨10.1016/j.tcs.2012.11.019⟩. ⟨ensl-00578527v9⟩