12 citations · 23 across the 13 of their papers we have counts for
10 papers · 1 filter
The Distribution of the Deepest Leaves in Binary Trees
Olivier Bodini, Antoine Genitrini, Khaydar Nurligareev
We study the extreme local structure of plane binary trees through the limiting distribution of the number of leaves at maximum depth. For every , we determine the limiting…
Growing Binary Trees
Olivier Bodini, Antoine Genitrini, Khaydar Nurligareev
This paper introduces a new combinatorial framework for modeling the growth of binary trees through a discrete evolution process that incorporates a growing rule and an extinction…
Compaction for two models of logarithmic-depth trees: Analysis and Experiments
Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger +2
We are interested in the quantitative analysis of the compaction ratio for two classical families of trees: recursive trees and plane binary increasing trees. These families are ty…
On the Number of Increasing Trees with Label Repetitions
Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger +1
We study the asymptotic number of certain monotonically labeled increasing trees arising from a generalized evolution process. The main difference between the presented model and t…
Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height
Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers +1
A compacted binary tree is a graph created from a binary tree such that repeatedly occurring subtrees in the original tree are represented by pointers to existing ones, and hence e…
Full asymptotic expansion for Polya structures
Antoine Genitrini
In order to obtain the full asymptotic expansion for Polya trees, i.e. rooted unlabelled and non-plane trees, Flajolet and Sedgewick observed that their specification could be seen…
Generalised and Quotient Models for Random And/Or Trees and Application to Satisfiability
Antoine Genitrini, Cécile Mailler
This article is motivated by the following satisfiability question: pick uniformly at random an and/or Boolean expression of length n, built on a set of k_n Boolean variables. What…
The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
Antoine Genitrini, Bernhard Gittenberger, Veronika Kraus +1
We consider a probability distribution on the set of Boolean functions in n variables which is induced by random Boolean expressions. Such an expression is a random rooted plane tr…
Associative and commutative tree representations for Boolean functions
Antoine Genitrini, Bernhard Gittenberger, Veronika Kraus +1
Since the 90's, several authors have studied a probability distribution on the set of Boolean functions on variables induced by some probability distributions on formulas built…
Catalan satisfiability problem
Antoine Genitrini, Cécile Mailler
An and/or tree is usually a binary plane tree, with internal nodes labelled by logical connectives, and with leaves labelled by literals chosen in a fixed set of k variables and th…