12 citations · 23 across the 13 of their papers we have counts for
16 papers
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…
An iterative approach for counting reduced ordered binary decision diagrams
Julien Clément, Antoine Genitrini
For three decades binary decision diagrams, a data structure efficiently representing Boolean functions, have been widely used in many distinct contexts like model verification, ma…
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…
The Combinatorics of Barrier Synchronization
Olivier Bodini, Matthieu Dien, Antoine Genitrini +1
In this paper we study the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executi…
Binary Decision Diagrams: from Tree Compaction to Sampling
Julien Clément, Antoine Genitrini
Any Boolean function corresponds with a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a direct acyclic graph where common…
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…
Ranked Schröder Trees
Olivier Bodini, Antoine Genitrini, Mehdi Naima
In biology, a phylogenetic tree is a tool to represent the evolutionary relationship between species. Unfortunately, the classical Schröder tree model is not adapted to take into a…
Beyond series-parallel concurrent systems: the case of arch processes
Olivier Bodini, Matthieu Dien, Antoine Genitrini +1
In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allow…
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…
A Quantitative Study of Pure Parallel Processes
Olivier Bodini, Antoine Genitrini, Frédéric Peschanski
In this paper, we study the interleaving -- or pure merge -- operator that most often characterizes parallelism in concurrency theory. This operator is a principal cause of the so-…
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…