Jagiellonian University Repository

On the enumeration of closures and environments with an application to random generation

pcg.skipToMenu

On the enumeration of closures and environments with an application to random generation

Show full item record

dc.contributor.author Bendkowski, Maciej [SAP14013025] pl
dc.contributor.author Lescanne, Pierre pl
dc.date.accessioned 2019-11-22T11:35:53Z
dc.date.available 2019-11-22T11:35:53Z
dc.date.issued 2019 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/87717
dc.language eng pl
dc.rights Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa *
dc.rights.uri http://creativecommons.org/licenses/by/4.0/pl/legalcode *
dc.title On the enumeration of closures and environments with an application to random generation pl
dc.type JournalArticle pl
dc.description.physical 3:1-3:21 pl
dc.abstract.pl 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. pl
dc.subject.en lambda-calculus pl
dc.subject.en combinatorics pl
dc.subject.en functional programming pl
dc.subject.en mathematical analysis pl
dc.subject.en complexity pl
dc.description.volume 15 pl
dc.description.number 4 pl
dc.identifier.doi 10.23638/LMCS-15(4:3)2019 pl
dc.identifier.eissn 1860-5974 pl
dc.title.journal Logical Methods in Computer Science pl
dc.language.container eng pl
dc.affiliation Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej pl
dc.subtype Article pl
dc.rights.original CC-BY; otwarte czasopismo; ostateczna wersja wydawcy; w momencie opublikowania; 0 pl
dc.identifier.project 2016/21/N/ST6/01032 pl
dc.identifier.project ROD UJ / OP pl
.pointsMNiSW [2019 A]: 70


Files in this item

This item appears in the following Collection(s)

Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa Except where otherwise noted, this item's license is described as Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa