Infinite labeled trees: From rational to Sturmian trees

Nicolas Gast 1, 2 Bruno Gaujal 1, 2
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : This paper studies infinite unordered d-ary trees with nodes labeled by {0, 1}. We introduce the notions of rational and Sturmian trees along with the definitions of (strongly) balanced trees and mechanical trees, and study the relations among them. In particular, we show that (strongly) balanced trees exist and coincide with mechanical trees in the irrational case, providing an effective construction. Such trees also have a minimal factor complexity, hence are Sturmian. We also give several examples illustrating the inclusion relations between these classes of trees.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2010, 411, pp.1146 - 1166. 〈10.1016/j.tcs.2009.12.009〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01086034
Contributeur : Nicolas Gast <>
Soumis le : vendredi 21 novembre 2014 - 16:27:25
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : vendredi 14 avril 2017 - 19:19:29

Fichier

tcs-GastGaujal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Nicolas Gast, Bruno Gaujal. Infinite labeled trees: From rational to Sturmian trees. Theoretical Computer Science, Elsevier, 2010, 411, pp.1146 - 1166. 〈10.1016/j.tcs.2009.12.009〉. 〈hal-01086034〉

Partager

Métriques

Consultations de la notice

391

Téléchargements de fichiers

89