Balanced Labeled Trees: Density, Complexity and Mechanicity

Nicolas Gast 1 Bruno Gaujal 1
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : 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.
Type de document :
Rapport
[Research Report] RR-6240, INRIA. 2007, pp.25
Liste complète des métadonnées

https://hal.inria.fr/inria-00159564
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 4 juillet 2007 - 14:31:49
Dernière modification le : jeudi 11 octobre 2018 - 08:48:02
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:37:47

Fichiers

RR-6240.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00159564, version 2

Collections

Citation

Nicolas Gast, Bruno Gaujal. Balanced Labeled Trees: Density, Complexity and Mechanicity. [Research Report] RR-6240, INRIA. 2007, pp.25. 〈inria-00159564v2〉

Partager

Métriques

Consultations de la notice

281

Téléchargements de fichiers

127