W dniach od 2 kwietnia do 5 kwietnia 2024 r. prowadzone będą prace związane z wdrożeniem nowej wersji systemu Repozytorium UJ. Nie będzie możliwe wprowadzanie nowych informacji do repozytorium. Za utrudnienia przepraszamy.
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