solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看4766次
Counting Environments and Closures. (arXiv:1802.00640v1 [cs.LO])
来源于:arXiv
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. 查看全文>>