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

Abstract

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

How to cite

top

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

Citations in EuDML Documents

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

NotesEmbed ?

top

You must be logged in to post comments.