Return words in Sturmian and episturmian words

Issue		RAIRO-Theor. Inf. Appl. Volume 34, Number 5, September-October 2000


Page(s)		343 - 356
DOI		10.1051/ita:2000121

DOI: 10.1051/ita:2000121
Theoret. Informatics Appl. 34 (2000) 343-356

Return words in Sturmian and episturmian words

Jacques Justin
IAFA, Université Paris VII, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; (Jacques.Justin@liafa.jussieu.fr)

Laurent Vuillon
IAFA, Université Paris VII, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; (Laurent.Vuillon@liafa.jussieu.fr)

Received May 2000. Accepted December 19, 2000.

Abstract: 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 wand 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.

AMS Subject Classification: 68R15

Communicated by: J. Karhumäki.

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.