Geodesic
The height of the Lyndon tree
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2013_special_264_a41,
     author = {Mercier, Lucas and Chassaing, Philippe},
     title = {The height of the {Lyndon} tree},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)},
     year = {2013},
     doi = {10.46298/dmtcs.2357},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2357/}
}
TY  - JOUR
AU  - Mercier, Lucas
AU  - Chassaing, Philippe
TI  - The height of the Lyndon tree
JO  - Discrete mathematics & theoretical computer science
PY  - 2013
VL  - DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2357/
DO  - 10.46298/dmtcs.2357
LA  - en
ID  - DMTCS_2013_special_264_a41
ER  - 
%0 Journal Article
%A Mercier, Lucas
%A Chassaing, Philippe
%T The height of the Lyndon tree
%J Discrete mathematics & theoretical computer science
%D 2013
%V DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2357/
%R 10.46298/dmtcs.2357
%G en
%F DMTCS_2013_special_264_a41
Mercier, Lucas; Chassaing, Philippe. The height of the Lyndon tree. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013). doi : 10.46298/dmtcs.2357. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2357/

Cité par Sources :