Asymptotically almost all \lambda-terms are strongly normalizing

Autor: Christophe Raffalli, Katarzyna Grygiel, Henk Barendregt, René David, Jakub Kozik, Guillaume Theyssier, Marek Zaionc
Přispěvatelé: Laboratoire de Mathématiques (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Theoretical Computer Science Department [Krakow] (TCS), Uniwersytet Jagielloński w Krakowie = Jagiellonian University (UJ)
Jazyk: angličtina
Rok vydání: 2009
Předmět:
Pure mathematics
Computer Science - Logic in Computer Science
General Computer Science
randomness
G.2.1
strong normalization
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Lambda
Translation (geometry)
01 natural sciences
Theoretical Computer Science
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
0202 electrical engineering
electronic engineering
information engineering
Mathematics - Combinatorics
Almost surely
Randomness
computer.programming_language
Mathematics
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
020207 software engineering
Mathematics - Logic
lambda-calculus
combinatory logic
Term (logic)
[MATH.MATH-LO]Mathematics [math]/Logic [math.LO]
010201 computation theory & mathematics
Combinatory logic
Lambda calculus
computer
Computer Science - Discrete Mathematics
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: