文章基本信息

标题：Asymptotically almost all Î»-terms are strongly normalizing
本地全文：下载
作者：René David ; Katarzyna Grygiel ; Jakub Kozik 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2013
卷号：9
期号：1
页码：1
DOI：10.2168/LMCS-9(1:2)2013
出版社：Technical University of Braunschweig
摘要：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.
其他关键词：lambda-calculus, combinatorics, normalisation, combinatory logic.