René David ; Katarzyna Grygiel ; Jakub Kozic ; Christophe Raffalli ; Guillaume Theyssier et al. - Asymptotically almost all \lambda-terms are strongly normalizing

lmcs:848 - Logical Methods in Computer Science, February 15, 2013, Volume 9, Issue 1 - https://doi.org/10.2168/LMCS-9(1:2)2013
Asymptotically almost all \lambda-terms are strongly normalizingArticle

Authors: René David ; Katarzyna Grygiel ; Jakub Kozik ORCID; Christophe Raffalli ; Guillaume Theyssier ; Marek Zaionc

    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.

    https://doi.org/10.2168/LMCS-9(1:2)2013
    Source: arXiv.org:0903.5505
    Volume: Volume 9, Issue 1
    Published on: February 15, 2013
    Imported on: September 27, 2010
    Keywords: Mathematics - Logic, Computer Science - Discrete Mathematics, Computer Science - Logic in Computer Science, Mathematics - Combinatorics, G.2.1
    Licence: arXiv.org - Non-exclusive license to distribute

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Publications

    Has review
    • 1 zbMATH Open

    8 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 3034 times.
    This article's PDF has been downloaded 612 times.