Infinite labeled trees: From rational to Sturmian trees

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.


Published in:
Theoretical Computer Science, 411, 7-9, 1146-1166
Year:
2010
Publisher:
Elsevier
ISSN:
0304-3975
Laboratories:




 Record created 2013-02-05, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)