How to count linear and affine closed lambda terms?
Author: Pierre Lescanne
Paper Information
| Title: | How to count linear and affine closed lambda terms? |
| Authors: | Pierre Lescanne |
| Proceedings: | Linearity/TLLA Pre-proceedings |
| Editors: | Maribel Fernandez, Valeria de Paiva, Thomas Ehrhard and Lorenzo Tortora De Falco |
| Keywords: | linear term, affine term, combinatoric, lambda calculus |
| Abstract: | ABSTRACT. Affine lambda-terms are lambda-terms in which each bound variable occurs at most once and linear lambda-terms are lambda-terms in which each bound variable occurs once and only once. In this paper we count the number of affine closed lambda-terms of size n, linear closed lambda-terms of size n, affine closed beta-normal forms of size n and linear closed beta-normal forms of size n, for several measures of the size of lambda-terms. From these formulas, we show how we can derive programs for generating all the terms of size n for each class. The foundation of all of this is a specific data structure, made of contexts in which one counts all the holes at each level of abstractions by lambda's. |
| Pages: | 6 |
| Talk: | Jul 08 09:20 (Session 34J) |
| Paper: | ![]() |
