Skip to Main content Skip to Navigation
Journal articles

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 [2007-2015]
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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01086034
Contributor : Nicolas Gast <>
Submitted on : Friday, November 21, 2014 - 4:27:25 PM
Last modification on : Thursday, July 9, 2020 - 9:44:38 AM
Document(s) archivé(s) le : Friday, April 14, 2017 - 7:19:29 PM

File

tcs-GastGaujal.pdf
Files produced by the author(s)

Identifiers

Collections

CNRS | INRIA | LIG | UGA

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⟩

Share

Metrics

Record views

504

Files downloads

282