Title: Parameter studies on random trees and lambda terms
Language: English
Authors: Larcher, Isabella 
Qualification level: Doctoral
Keywords: random trees; lambda terms; asymptotic enumeration
Advisor: Gittenberger, Bernhard 
Issue Date: 2020
Number of Pages: 153
Qualification level: Doctoral
Abstract: 
This thesis is devoted to asymptotic parameter studies of different combinatorial classes. Thereby the key tools are the concept of generating functions, the symbolic method and singularity analysis. A part of the thesis is devoted to the analysis of tree parameters: We derive asymptotic mean and variance of the protection number of a random tree as well as of a random vertex. in simply generated trees, Polya trees and non-plane binary trees. Then, we compute the avaérage number of non-isomorphic subtree-shapes for two selected classes of increasingly labeled trees. Last, we investigate the average number of embeddings of a given rooted tree into different classes of trees, namely plane and non-plane binary trees and planted plane trees. The last part treats the analysis of shape parameters of special subclasses of lambda terms that are restricted by a bounded length of each binding or a bounded length number of nested abstractions, respectively. In particular, we are able to explain the unusual behaviour of the counting sequence of the latter class by providing their asymptotic unary profile.
URI: https://doi.org/10.34726/hss.2020.74181
http://hdl.handle.net/20.500.12708/14962
DOI: 10.34726/hss.2020.74181
Library ID: AC15670824
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Parameter studies on random trees and lambda terms.pdf3.72 MBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

37
checked on Mar 1, 2021

Download(s)

40
checked on Mar 1, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.