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 metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619760
Contributor : Jean Berstel <>
Submitted on : Thursday, October 6, 2011 - 2:06:16 PM
Last modification on : Friday, March 27, 2020 - 3:07:01 AM
Long-term archiving on: : Saturday, January 7, 2012 - 2:20:51 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619760, version 1

Citation

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

Share

Metrics

Record views

268

Files downloads

193