Skip to Main content Skip to Navigation
Journal articles

Infinite labeled trees: From rational to Sturmian trees

Nicolas Gast 1 Bruno Gaujal 1
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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Nicolas Gast Connect in order to contact the contributor
Submitted on : Friday, November 21, 2014 - 4:27:25 PM
Last modification on : Thursday, October 21, 2021 - 3:49:25 AM
Long-term archiving on: : Friday, April 14, 2017 - 7:19:29 PM


Files produced by the author(s)




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⟩



Les métriques sont temporairement indisponibles