Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics
| Autor: | Alexandros Singh, Antoine Genitrini, Olivier Bodini, Mehdi Naima |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Algorithmes, Programmes et Résolution (APR), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Henning Fernau, ANR-15-CE40-0014,MétAConC,Méthodes analytiques non conventionnelles en Combinatoire(2015) |
| Rok vydání: | 2020 |
| Předmět: |
Theoretical computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 010102 general mathematics Probabilistic logic Evolution process Monotonic function Increasing trees 0102 computer and information sciences Borel transform Data structure Asymptotic enumeration 01 natural sciences Tree (graph theory) Constraint (information theory) Monotonic trees Discrete time and continuous time 010201 computation theory & mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Node (computer science) Analytic combinatorics 0101 mathematics Analytic Combinatorics |
| Zdroj: | Computer Science – Theory and Applications ISBN: 9783030500252 CSR Computer Science-Theory and Applications-15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings Computer Science – Theory and Applications 15th International Computer Science Symposium 15th International Computer Science Symposium, Jun 2020, Yekaterinburg, Russia. pp.155-168, ⟨10.1007/978-3-030-50026-9_11⟩ |
| DOI: | 10.1007/978-3-030-50026-9_11 |
| Popis: | International audience; There exists a wealth of literature concerning families of increasing trees, particularly suitable for representing the evolution of either data structures in computer science, or probabilistic urns in mathematics, but are also adapted to model evolutionary trees in biology. The classical notion of increasing trees corresponds to labeled trees such that, along paths from the root to any leaf, node labels are strictly increasing; in addition nodes have distinct labels. In this paper we introduce new families of increasingly labeled trees relaxing the constraint of unicity of each label. Such models are especially useful to characterize processes evolving in discrete time whose nodes evolve simultaneously. In particular, we obtain growth processes for biology much more adequate than the previous increasing models. The families of monotonic trees we introduce are much more delicate to deal with, since they are not decomposable in the sense of Analytic Combinatorics. New tools are required to study the quantitative statistics of such families. In this paper, we first present a way to combinatorially specify such families through evolution processes, then, we study the tree enumerations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|