Skip to Main content Skip to Navigation
Conference papers

The height of the Lyndon tree

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229697
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:20:07 AM
Last modification on : Tuesday, March 2, 2021 - 5:12:06 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:41:02 AM

File

dmAS0181.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229697, version 1

Collections

Citation

Lucas Mercier, Philippe Chassaing. The height of the Lyndon tree. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.957-968. ⟨hal-01229697⟩

Share

Metrics

Record views

173

Files downloads

572