Katarzyna Grygiel ; Isabella Larcher - Unary profile of lambda terms with restricted De Bruijn indices

dmtcs:5836 - Discrete Mathematics & Theoretical Computer Science, February 12, 2021, vol. 22 no. 3, Computational Logic and Applications (CLA'19) - https://doi.org/10.46298/dmtcs.5836
Unary profile of lambda terms with restricted De Bruijn indices

Authors: Katarzyna Grygiel 1,2; Isabella Larcher 2

In this paper we present an average-case analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the so-called hat of the term, to which some number of k-colored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of k-colored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal non-empty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms.

Volume: vol. 22 no. 3, Computational Logic and Applications (CLA'19)
Section: Special issues
Published on: February 12, 2021
Accepted on: January 13, 2021
Submitted on: October 14, 2019
Keywords: lambda terms with restrictions,singularity analysis,profile of lambda terms,[MATH]Mathematics [math],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1805.09419
Source : ScholeXplorer IsRelatedTo DOI 10.37236/8491
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1805.09419
  • 1805.09419
  • 10.37236/8491
  • 10.37236/8491
  • 10.48550/arxiv.1805.09419
Statistical properties of lambda terms

Consultation statistics

This page has been seen 334 times.
This article's PDF has been downloaded 185 times.