Skip to Main content Skip to Navigation
Journal articles

Sturmian Trees

Abstract : 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 prove that a tree is Sturmian if and only if the minimal automaton associated to its language is slow, that is if the Moore minimization algorithm splits exactly one equivalence class at each step. We give various examples of Sturmian trees, and we introduce two parameters on Sturmian trees, called the degree and the rank. We show that there is no Sturmian tree of finite degree at least 2 and having finite rank. We characterize the family of Sturmian trees of degree 1 and having finite rank by means of a structural property of their minimal automata.
Document type :
Journal articles
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Jean Berstel Connect in order to contact the contributor
Submitted on : Thursday, October 6, 2011 - 2:06:16 PM
Last modification on : Saturday, January 15, 2022 - 3:59:31 AM
Long-term archiving on: : Saturday, January 7, 2012 - 2:20:51 AM


Files produced by the author(s)


  • HAL Id : hal-00619760, version 1


Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot. Sturmian Trees. Theory of Computing Systems, Springer Verlag, 2010, 46 (3), pp.443-478. ⟨hal-00619760⟩



Record views


Files downloads