The height of the Lyndon tree

Lucas Mercier 1 Philippe Chassaing 1
1 Probabilités et statistiques
IECL - Institut Élie Cartan de Lorraine
Abstract : We consider the set $\mathcal{L}_n<$ of n-letters long Lyndon words on the alphabet $\mathcal{A}=\{0,1\}$. For a random uniform element ${L_n}$ of the set $\mathcal{L}_n$, the binary tree $\mathfrak{L} (L_n)$ obtained by successive standard factorization of $L_n$ and of the factors produced by these factorization is the $\textit{Lyndon tree}$ of $L_n$. We prove that the height $H_n$ of $\mathfrak{L} (L_n)$ satisfies $\lim \limits_n \frac{H_n}{\mathsf{ln}n}=\Delta$, in which the constant $\Delta$ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers ($\Delta ≃5.092\dots $). The convergence is the convergence in probability of random variables.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.957-968, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229697
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:20:07
Dernière modification le : jeudi 11 janvier 2018 - 06:26:22
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:41:02

Fichier

dmAS0181.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229697, version 1

Collections

Citation

Lucas Mercier, Philippe Chassaing. The height of the Lyndon tree. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.957-968, 2013, DMTCS Proceedings. 〈hal-01229697〉

Partager

Métriques

Consultations de la notice

136

Téléchargements de fichiers

175