Sturmian Trees - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Theory of Computing Systems Année : 2010

Sturmian Trees

Résumé

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.
Fichier principal
Vignette du fichier
hal.pdf (1.14 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619760 , version 1 (06-10-2011)

Identifiants

  • HAL Id : hal-00619760 , version 1

Citer

Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot. Sturmian Trees. Theory of Computing Systems, 2010, 46 (3), pp.443-478. ⟨hal-00619760⟩
112 Consultations
141 Téléchargements

Partager

Gmail Facebook X LinkedIn More