by Jean Berstel, Luc Boasson, Olivier Carton and Isabelle Fagnot
Les arbres sturmiens sont une généralisation naturelle des mots sturmiens. Un arbre binaire étiqueté est sturmien s'il possède n+1 sous-arbres distincts de hauteur n pour tout n. Ce sont les arbres iirrationnels de complexité minimale. On donne des exemples variés d'arbres sturmiens, montrant que la situation est bien plus compliquée que pour les mots. L'automate minimal infini naturellement associé à un mot sturmien a d'intéressantes propriétés. Deux paramètres naturels semblent caractériser des familles d'arbres sturmiens; nous les appelons rang et degré. Nous caractérisons la famille d'arbres sturmiens de degré 1 et de rang fini par une propriété structurelle de leurs automates.
We consider Sturmian trees as a natural generalization of Sturmian words. A Sturmian tree is a tree having n+1 distinct subtrees of height n for each n. As for the case of words, Sturmian trees are irrational trees of minimal complexity. We give various examples of Sturmian trees, and we characterize one family of Sturmian trees by means of a structural property of their automata.