Institut für Mathematik
In previous work, several deterministic reduction procedures on plane
trees (e.g. cutting away all leaves or cutting away all maximal paths
ending in a leaf) have been studied. In this context, a parameter of
particular interest is the number of removed nodes after iteratively
applying the reduction a fixed number of times to a given plane tree.
After briefly revisiting the previous results, we will discuss a new
modeling approach based on a recursive description using additive tree
parameters. Effectively, this new strategy leads to functional equations
for the appropriate bivariate generating functions and thus allows us to
analyze the behavior of a deterministic reduction acting on tree classes
that are not part of the Catalan family. In the scope of this talk we
will focus on the „cutting leaves“-reduction applied to the class of
simply generated trees (i.e., a generalization of plane trees) and the
class of Pólya trees (unordered, rooted trees).
Senka Haznadar (senka [dot] omerhodzic [at] aau [dot] at)