DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2018.25

On the Number of Variables in Special Classes of Random Lambda-Terms

Authors: Bernhard Gittenberger and Isabella Larcher

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract

We investigate the number of variables in two special subclasses of lambda-terms that are restricted by a bound of the number of abstractions between a variable and its binding lambda, and by a bound of the nesting levels of abstractions, respectively. These restrictions are on the one hand very natural from a practical point of view, and on the other hand they simplify the counting problem compared to that of unrestricted lambda-terms in such a way that the common methods of analytic combinatorics are applicable. We will show that the total number of variables is asymptotically normally distributed for both subclasses of lambda-terms with mean and variance asymptotically equal to C_1 n and C_2 n, respectively, where the constants C_1 and C_2 depend on the bound that has been imposed. So far we just derived closed formulas for the constants in case of the class of lambda-terms with a bounded number of abstractions between each variable and its binding lambda. However, for the other class of lambda-terms that we consider, namely lambda-terms with a bounded number of nesting levels of abstractions, we investigate the number of variables in the different abstraction levels and thereby exhibit very interesting results concerning the distribution of the variables within those lambda-terms.

Cite as

Bernhard Gittenberger and Isabella Larcher. On the Number of Variables in Special Classes of Random Lambda-Terms. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gittenberger_et_al:LIPIcs.AofA.2018.25,
  author =	{Gittenberger, Bernhard and Larcher, Isabella},
  title =	{{On the Number of Variables in Special Classes of Random Lambda-Terms}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.25},
  URN =		{urn:nbn:de:0030-drops-89180},
  doi =		{10.4230/LIPIcs.AofA.2018.25},
  annote =	{Keywords: lambda-terms, directed acyclic graphs, singularity analysis, limiting distributions}
}

Search Results

Documents authored by Larcher, Isabella

On the Number of Variables in Special Classes of Random Lambda-Terms

Abstract

Cite as

Thanks for your feedback!

Could not send message