David, René and Grygiel, Katarzyna and Kozic, Jakub and Raffalli, Christophe and Theyssier, Guillaumeet al. - Asymptotically almost all \lambda-terms are strongly normalizing

lmcs:848 - Logical Methods in Computer Science, February 15, 2013, Volume 9, Issue 1
Asymptotically almost all \lambda-terms are strongly normalizing

Authors: David, René and Grygiel, Katarzyna and Kozic, Jakub and Raffalli, Christophe and Theyssier, Guillaume and Zaionc, Marek

We present quantitative analysis of various (syntactic and behavioral) properties of random \lambda-terms. Our main results are that asymptotically all the terms are strongly normalizing and that any fixed closed term almost never appears in a random term. Surprisingly, in combinatory logic (the translation of the \lambda-calculus into combinators), the result is exactly opposite. We show that almost all terms are not strongly normalizing. This is due to the fact that any fixed combinator almost always appears in a random combinator.


Source : oai:arXiv.org:0903.5505
DOI : 10.2168/LMCS-9(1:2)2013
Volume: Volume 9, Issue 1
Published on: February 15, 2013
Submitted on: September 27, 2010
Keywords: Mathematics - Logic,Computer Science - Discrete Mathematics,Computer Science - Logic in Computer Science,Mathematics - Combinatorics,G.2.1


Share

Consultation statistics

This page has been seen 80 times.
This article's PDF has been downloaded 61 times.