Title: On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height
Language: English
Authors: Bodini, Olivier 
Gardy, Daniele 
Gittenberger, Bernhard
Golebiewski, Zbigniew 
Category: Research Article
Issue Date: 2018
Journal: Annals of Combinatorics
ISSN: 0218-0006
We investigate 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.
Keywords: asymptotic enumeration; generating functions; lambda-terms; trees; directed acyclic graphs; nested square-roots; singularity analysis
DOI: 10.1007/s00026-018-0371-7
Library ID: AC15321018
URN: urn:nbn:at:at-ubtuw:3-5026
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Article
Appears in Collections:Article

Files in this item:

Show full item record

Page view(s)

checked on Jun 12, 2021


checked on Jun 12, 2021

Google ScholarTM


This item is licensed under a Creative Commons License Creative Commons