Combinatorics on recurrent words with subword complexity n+2.

Idrissa Kaboré; Théodore Tapsoba

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 4, page 425-446
  • ISSN: 0988-3754

Abstract

top
We state some new properties on Sturmian words and classify words which have, for any nonnegative integer n, exactly n+2 subwords of length n. We also define the notion of k by k insertion on infinite words and we give a formula for the complexity function of words obtained by applying that notion to Sturmian words. Lastly we study balance property and palindrome complexity of a subclass of words with complexity n+2 called quasi-Sturmian words by insertion; we give a characterization of this subclass with Parikh vectors.

How to cite

top

Kaboré, Idrissa, and Tapsoba, Théodore. "Combinatoire de mots récurrents de complexité n+2." RAIRO - Theoretical Informatics and Applications 41.4 (2007): 425-446. <http://eudml.org/doc/250055>.

@article{Kaboré2007,
abstract = {Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul n, exactement n+2 facteurs de longueur n. Nous définissons également la notion d'insertion k à k sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l'équilibre et la palindromie d'une classe particulière de mots de complexité n+2 que nous appelons mots quasi-sturmiens par insertion et que nous caractérisons à l'aide des vecteurs de Parikh. },
author = {Kaboré, Idrissa, Tapsoba, Théodore},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Mot sturmien; complexité; mot quasi-sturmien par insertion},
language = {fre},
month = {9},
number = {4},
pages = {425-446},
publisher = {EDP Sciences},
title = {Combinatoire de mots récurrents de complexité n+2},
url = {http://eudml.org/doc/250055},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Kaboré, Idrissa
AU - Tapsoba, Théodore
TI - Combinatoire de mots récurrents de complexité n+2
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/9//
PB - EDP Sciences
VL - 41
IS - 4
SP - 425
EP - 446
AB - Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul n, exactement n+2 facteurs de longueur n. Nous définissons également la notion d'insertion k à k sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l'équilibre et la palindromie d'une classe particulière de mots de complexité n+2 que nous appelons mots quasi-sturmiens par insertion et que nous caractérisons à l'aide des vecteurs de Parikh.
LA - fre
KW - Mot sturmien; complexité; mot quasi-sturmien par insertion
UR - http://eudml.org/doc/250055
ER -

References

top
  1. P. Alessandri, Classification et représentation des mots de complexité n + 2. Rapport technique, Université Aix-Marseille II (1995).  
  2. P. Alessandri, Codage de rotations et basses complexités. Thèse, Université Aix-Marseille II (1996).  
  3. J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. Simon Stevin1 (1994) 133–143.  
  4. J.-P. Allouche, M. Baake, J. Cassaigne et D. Damanik, Palindrome complexity. Theoret. Comput. Sci.292 (2003) 9–31.  
  5. V. Berthée, Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci.165 (1996) 295–309.  
  6. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  
  7. J. Cassaigne, Sequences with grouped factors, in Developments in Language Theory III (DLT'97), pp. 211–222, Aristotle University af Thessaloniki (1998).  
  8. E.M. Coven, Sequences with minimal block growth. Math. Syst. Theory8 (1975) 376–382.  
  9. E.M. Coven et G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theory7 (1973) 138–153.  
  10. G. Didier, Caractérisation des N-écritures et application à l'étude des suites de complexité ultimement n + Cste. Theoret. Comput. Sci.215 (1999) 31–49.  
  11. X. Droubay et G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci.223 (1999) 73–85.  
  12. S. Dulucq et D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm. Theoret. comput. Sci. 71 (1990) 381–400.  
  13. S. Ferenczi et C. Mauduit, Transcendency of numbers with a low complexity expansion. J. Number Theory67 (1997) 146–161.  
  14. A. Heinis, Arithmetics and combinatorics of words of low complexity. Ph.D. Thesis, University of Leiden (2001).  
  15. M. Lothaire, Algebraic combinatorics on words, vol. 90 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2002).  
  16. F. Mignosi et P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux5 (1993) 221–233.  
  17. M. Morse et G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866.  
  18. M. Morse et G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42.  
  19. M.E. Paul, Minimal symbolic flows having minimal block growth. Math. Syst. Theory8 (1975) 309–315.  
  20. N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics. Lect. Notes Math.1794 (2002).  
  21. G. Rauzy, Suites à termes dans un alphabet fini. Sémin. Théor. Nombres Bordeaux25 (1982–1983) 1–16.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.