Balanced Labeled Trees: Density, Complexity and Mechanicity - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Balanced Labeled Trees: Density, Complexity and Mechanicity

Nicolas Gast
Bruno Gaujal

Résumé

Sturmian words are very particular infinite words with many equivalent definitions: minimal complexity of aperiodic sequences, balanced sequences and mechanical words. One natural way to generalize the first definition to trees is to consider planar trees of complexity n+1 but in doing so, one looses the other two properties. In this paper we will study non-planar trees. In this case, we show that strongly balanced trees are exactly mechanical trees. Moreover we will see that they are also aperiodic trees of minimal complexity, so that the three equivalent definitions of Sturmian words are almost preserved for non planar trees.
Fichier principal
Vignette du fichier
RR-6240.pdf (330.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00159564 , version 1 (03-07-2007)
inria-00159564 , version 2 (04-07-2007)

Identifiants

  • HAL Id : inria-00159564 , version 2

Citer

Nicolas Gast, Bruno Gaujal. Balanced Labeled Trees: Density, Complexity and Mechanicity. [Research Report] RR-6240, INRIA. 2007, pp.25. ⟨inria-00159564v2⟩
120 Consultations
94 Téléchargements

Partager

Gmail Facebook X LinkedIn More