Source author record

Zbigniew Gołębiewski

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Logic in Computer Science math.LO

Catalog footprint

Research overview

2works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

On the number of lambda terms with prescribed size of their De Bruijn representation

John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of binary words. Later, Grygiel and Lescanne conjectured that the number of binary lambda terms with $m$ free indices and of size $n$ (encoded as binary words of length $n$ ) is $o(n^{-3/2} τ^{-n})$ for $τ\approx 1.963448\ldots$ . We generalize the proposed notion of size and show that for several classes of lambda terms, including binary lambda terms with $m$ free indices, the number of terms of size $n$ is $Θ(n^{-3/2} ρ^{-n})$ with some class dependent constant $ρ$ , which in particular disproves the above mentioned conjecture. A way to obtain lower and upper bounds for the constant near the leading term is presented and numerical results for a few previously introduced classes of lambda terms are given.

preprint2015arXiv

On the number of unary-binary tree-like structures with restrictions on the unary height

We consider various classes of Motzkin trees as well as lambda-terms for which we derive asymptotic enumeration results. These classes are defined through various restrictions concerning the unary nodes or abstractions, respectively: We either bound their number or the allowed levels of nesting. The enumeration is done by means of a generating function approach and singularity analysis. The generating functions are composed of nested square roots and exhibit unexpected phenomena in some of the cases. Furthermore, we present some observations obtained from generating such terms randomly and explain why usually powerful tools for random generation, such as Boltzmann samplers, face serious difficulties in generating lambda-terms.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.