A natural counting of lambda terms
Tytuł:
A natural counting of lambda terms
Czasopismo:
Rok:
2016
Opis:
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 plai
Strony:
183-194
Tom (seria wydawnicza):
9587
Numer DOI:
10.1007/978-3-662-49192-8_15
Link:
http://link.springer.com/chapter/10.1007/978-3-662-49192-8_15