Issue |
RAIRO-Theor. Inf. Appl.
Volume 34, Number 5, September/October 2000
|
|
---|---|---|
Page(s) | 343 - 356 | |
DOI | https://doi.org/10.1051/ita:2000121 | |
Published online | 15 April 2002 |
Return words in Sturmian and episturmian words
1
LIAFA, Université Paris VII,
Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France;
(Jacques.Justin@liafa.jussieu.fr)
2
LIAFA, Université Paris VII,
Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France;
(Laurent.Vuillon@liafa.jussieu.fr)
Received:
May
2000
Accepted:
19
December
2000
Considering each occurrence of a word w in a recurrent infinite word, we define the set of return words of w to be the set of all distinct words beginning with an occurrence of w and ending exactly just before the next occurrence of w in the infinite word. We give a simpler proof of the recent result (of the second author) that an infinite word is Sturmian if and only if each of its factors has exactly two return words in it. Then, considering episturmian infinite words, which are a natural generalization of Sturmian words, we study the position of the occurrences of any factor in such infinite words and we determinate the return words. At last, we apply these results in order to get a kind of balance property of episturmian words and to calculate the recurrence function of these words.
Résumé
Si l'on considère chaque occurrence d'un mot w dans un mot infini récurrent, on définit l'ensemble des mots de retour de w comme l'ensemble de tous les mots distincts débutant avec une occurrence de w et finissant juste avant l'occurrence suivante de w. Nous donnons une nouvelle démonstration d'un résultat établi récemment par le deuxième auteur : un mot infini est sturmien si et seulement si chacun de ses facteurs a exactement deux mots de retour. Nous étudions les mots épisturmiens qui sont une généralisation naturelle des mots sturmiens. Puis nous déterminons la position d'un facteur donné et ses mots de retour dans un mot épisturmien. Enfin nous appliquons ces méthodes pour obtenir une propriété d'équilibre pour les mots épisturmiens et calculer la fonction de récurrence de ces mots infinis.
Mathematics Subject Classification: 68R15
© EDP Sciences, 2000
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.