License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.25
URN: urn:nbn:de:0030-drops-89180
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8918/
Go to the corresponding LIPIcs Volume Portal

Gittenberger, Bernhard ; Larcher, Isabella

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

pdf-format:
LIPIcs-AofA-2018-25.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{gittenberger_et_al:LIPIcs:2018:8918,
  author =	{Bernhard Gittenberger and Isabella Larcher},
  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 =	{James Allen Fill and Mark Daniel Ward},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8918},
  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}
}

Keywords: lambda-terms, directed acyclic graphs, singularity analysis, limiting distributions
Collection: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Issue Date: 2018
Date of publication: 18.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI