<div class="csl-bib-body">
<div class="csl-entry">Bodini, O., Gardy, D., Gittenberger, B., & Golebiewski, Z. (2018). On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height. <i>Annals of Combinatorics</i>, <i>22</i>, 45–91. https://doi.org/10.1007/s00026-018-0371-7</div>
</div>
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.
en
dc.language
English
-
dc.language.iso
en
-
dc.publisher
Birkhäuser
-
dc.relation.ispartof
Annals of Combinatorics
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
asymptotic enumeration
en
dc.subject
generating functions
en
dc.subject
lambda-terms
en
dc.subject
trees
en
dc.subject
directed acyclic graphs
en
dc.subject
nested square-roots
en
dc.subject
singularity analysis
en
dc.title
On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height
en
dc.type
Article
en
dc.type
Artikel
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.contributor.affiliation
Université Paris Nord, Villetaneuse, France
-
dc.contributor.affiliation
University of Versailles Saint Quentin en Yvelines, Vélizy Villacoublay, France
-
dc.contributor.affiliation
Wrocław University of Science and Technology, Poland
-
dc.description.startpage
45
-
dc.description.endpage
91
-
dc.rights.holder
2018 The Author(s)
-
dc.type.category
Original Research Article
-
tuw.container.volume
22
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
tuw.version
vor
-
wb.publication.intCoWork
International Co-publication
-
dcterms.isPartOf.title
Annals of Combinatorics
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie
-
tuw.publisher.doi
10.1007/s00026-018-0371-7
-
dc.identifier.eissn
0219-3094
-
dc.identifier.libraryid
AC15321018
-
dc.description.numberOfPages
47
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:3-5026
-
dc.rights.identifier
CC BY 4.0
de
dc.rights.identifier
CC BY 4.0
en
wb.sci
true
-
item.openairecristype
http://purl.org/coar/resource_type/c_2df8fbb1
-
item.cerifentitytype
Publications
-
item.fulltext
with Fulltext
-
item.languageiso639-1
en
-
item.openairetype
research article
-
item.openaccessfulltext
Open Access
-
item.grantfulltext
open
-
crisitem.author.dept
University of Versailles Saint Quentin en Yvelines, Vélizy Villacoublay, France
-
crisitem.author.dept
E104-05 - Forschungsbereich Kombinatorik und Algorithmen
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie