# Return words in Sturmian and episturmian words

Jacques Justin; Laurent Vuillon

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 5, page 343-356
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topJustin, Jacques, and Vuillon, Laurent. "Return words in Sturmian and episturmian words." RAIRO - Theoretical Informatics and Applications 34.5 (2010): 343-356. <http://eudml.org/doc/222053>.

@article{Justin2010,

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 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.
},

author = {Justin, Jacques, Vuillon, Laurent},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {recurrent infinite word; episturmian words; recurrence function},

language = {eng},

month = {3},

number = {5},

pages = {343-356},

publisher = {EDP Sciences},

title = {Return words in Sturmian and episturmian words},

url = {http://eudml.org/doc/222053},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Justin, Jacques

AU - Vuillon, Laurent

TI - Return words in Sturmian and episturmian words

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 5

SP - 343

EP - 356

AB -
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.

LA - eng

KW - recurrent infinite word; episturmian words; recurrence function

UR - http://eudml.org/doc/222053

ER -

## References

top- J.-P. Allouche, J.L. Davison, M. Queffélec and L.Q. Zamboni, Transcendence of Sturmian or morphic continued fractions. Preprint (1999).
- P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n+1. Bull. Soc. Math. France119 (1991) 199-215.
- J. Berstel and P. Séébold, Sturmian words, edited by M. Lothaire, Algebraic combinatorics on Words (to appear).
- J. Cassaigne, Ideas for a proof of Rauzy's conjecture on the recurrence functions of infinite words, talk in Rouen ``words 1999''.
- N. Chekhova, P. Hubert and A. Messaoudi, Propriétés combinatoires,ergodiques et arithmétiques de la substitution de Tribonacci. Prepublication 98-24 IML.
- A. de Luca, Sturmian words: Structure, Combinatorics and their Arithmetics. Theoret. Comput. Sci.183 (1997) 45-82.
- X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of Rauzy and de Luca. Theoret. Comput. Sci. (to appear).
- F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998) 89-101.
- F. Durand, Contributions à l'étude des suites et systèmes dynamiques substitutifs. Ph.D. Thesis, Université de la Méditerranée, Aix-Marseille II (1996).
- I. Fagnot and L. Vuillon, Generalized balances in Sturmian words. Prepublication LIAFA 2000/02.
- G.A. Hedlund and M. Morse, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math.62 (1940) 1-42.
- C. Holton and L.Q. Zamboni, Geometric realizations of substitutions. Bull. Soc. Math. France126 (1998) 149-179.
- J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Prepublication LIAFA 2000/23.
- L. Vuillon, A characterization of Sturmian words by return words. European J. Combin.22 (2001) 263-275.

## Citations in EuDML Documents

top- Marcia Edson, Luca Q. Zamboni, On the Number of Partitions of an Integer in the $m$-bonacci Base
- Artūras Dubickas, Squares and cubes in Sturmian sequences
- Gwenael Richomme, Some algorithms to compute the conjugates of Episturmian morphisms
- Gwenael Richomme, Some algorithms to compute the conjugates of episturmian morphisms
- L'ubomíra Balková, Edita Pelantová, Štěpán Starosta, Sturmian jungle (or garden?) on multiliteral alphabets
- L'ubomíra Balková, Edita Pelantová, Štěpán Starosta, Sturmian jungle (or garden?) on multiliteral alphabets
- Amy Glen, Jacques Justin, Episturmian words: a survey

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.