Maciej Bendkowski ; Pierre Lescanne - On the enumeration of closures and environments with an application to random generation

lmcs:4998 - Logical Methods in Computer Science, October 17, 2019, Volume 15, Issue 4 - https://doi.org/10.23638/LMCS-15(4:3)2019
On the enumeration of closures and environments with an application to random generationArticle

Authors: Maciej Bendkowski ; Pierre Lescanne

    Environments and closures are two of the main ingredients of evaluation in lambda-calculus. A closure is a pair consisting of a lambda-term and an environment, whereas an environment is a list of lambda-terms assigned to free variables. In this paper we investigate some dynamic aspects of evaluation in lambda-calculus considering the quantitative, combinatorial properties of environments and closures. Focusing on two classes of environments and closures, namely the so-called plain and closed ones, we consider the problem of their asymptotic counting and effective random generation. We provide an asymptotic approximation of the number of both plain environments and closures of size $n$. Using the associated generating functions, we construct effective samplers for both classes of combinatorial structures. Finally, we discuss the related problem of asymptotic counting and random generation of closed environemnts and closures.


    Volume: Volume 15, Issue 4
    Published on: October 17, 2019
    Accepted on: September 3, 2019
    Submitted on: November 28, 2018
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1480 times.
    This article's PDF has been downloaded 326 times.