Document Open Access Logo

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

Authors Bernhard Gittenberger, Isabella Larcher

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.25.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Bernhard Gittenberger
  • Department of Discrete Mathematics and Geometry, Technische Universität Wien, Wiedner Hauptstraße 8-10/104, A-1040 Wien, Austria
Isabella Larcher
  • Department of Discrete Mathematics and Geometry, Technische Universität Wien, Wiedner Hauptstraße 8-10/104, A-1040 Wien, Austria

Funding

Supported by the Austrian Science Fund (FWF) grant SFB F50-03.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.AofA.2018.25

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Generating functions
  • Mathematics of computing → Enumeration
  • Mathematics of computing → Graph enumeration
Keywords
  • lambda-terms
  • directed acyclic graphs
  • singularity analysis
  • limiting distributions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Henk P. Barendregt. The lambda calculus, its syntax and semantics, volume 40 of Studies in Logic (London). College Publications, London, 2012. [Reprint of the 1984 revised edition, MR0774952], With addenda for the 6th imprinting, Mathematical Logic and Foundations. Google Scholar
  2. O. Bodini, D. Gardy, and A. Jacquot. Asymptotics and random sampling for BCI and BCK lambda terms. Theoret. Comput. Sci., 502:227-238, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.01.008.
  3. Olivier Bodini, Danièle Gardy, and Bernhard Gittenberger. Lambda terms of bounded unary height. In ANALCO11 - Workshop on Analytic Algorithmics and Combinatorics, pages 23-32. SIAM, Philadelphia, PA, 2011. Google Scholar
  4. Olivier Bodini, Danièle Gardy, Bernhard Gittenberger, and Zbigniew Gołębiewski. On the number of unary-binary tree-like structures with restrictions on the unary height. Ann. Combin., 2018. To appear. Google Scholar
  5. Olivier Bodini, Danièle Gardy, Bernhard Gittenberger, and Alice Jacquot. Enumeration of generalized BCI lambda-terms. Electron. J. Combin., 20(4):Paper 30, 23, 2013. Google Scholar
  6. Olivier Bodini and Bernhard Gittenberger. On the asymptotic number of BCK(2)-terms. In ANALCO14 - Meeting on Analytic Algorithmics and Combinatorics, pages 25-39. SIAM, Philadelphia, PA, 2014. URL: http://dx.doi.org/10.1137/1.9781611973204.3.
  7. Haskell Brooks Curry, Robert Feys, William Craig, J Roger Hindley, and Jonathan P Seldin. Combinatory logic, volume 1. North-Holland Amsterdam, 1958. Google Scholar
  8. Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009. URL: http://dx.doi.org/10.1017/CBO9780511801655.
  9. Katarzyna Grygiel, Pawe\l M. Idziak, and Marek Zaionc. How big is BCI fragment of BCK logic. J. Logic Comput., 23(3):673-691, 2013. URL: http://dx.doi.org/10.1093/logcom/exs017.
  10. H-K Hwang. On convergence rates in the central limit theorems for combinatorial structures. European Journal of Combinatorics, 19(3):329-343, 1998. Google Scholar
  11. Pierre Lescanne. On counting untyped lambda terms. Theoret. Comput. Sci., 474:80-97, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.11.019.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact