Infinite labeled trees: From rational to Sturmian trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2010

Infinite labeled trees: From rational to Sturmian trees

Nicolas Gast
Bruno Gaujal

Résumé

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.
Fichier principal
Vignette du fichier
tcs-GastGaujal.pdf (455.23 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01086034 , version 1 (21-11-2014)

Identifiants

Citer

Nicolas Gast, Bruno Gaujal. Infinite labeled trees: From rational to Sturmian trees. Theoretical Computer Science, 2010, 411, pp.1146 - 1166. ⟨10.1016/j.tcs.2009.12.009⟩. ⟨hal-01086034⟩
336 Consultations
137 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More