Sturmian jungle (or garden?) on multiliteral alphabets

L'ubomíra Balková; Edita Pelantová; Štěpán Starosta

RAIRO - Theoretical Informatics and Applications (2011)

  • Volume: 44, Issue: 4, page 443-470
  • ISSN: 0988-3754

Abstract

top
The properties characterizing Sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of Sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of Sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions of Sturmian words.

How to cite

top

Balková, L'ubomíra, Pelantová, Edita, and Starosta, Štěpán. "Sturmian jungle (or garden?) on multiliteral alphabets." RAIRO - Theoretical Informatics and Applications 44.4 (2011): 443-470. <http://eudml.org/doc/193070>.

@article{Balková2011,
abstract = { The properties characterizing Sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of Sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of Sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions of Sturmian words. },
author = {Balková, L'ubomíra, Pelantová, Edita, Starosta, Štěpán},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Sturmian words; generalizations of Sturmian words; palindromes; rich words; rich words},
language = {eng},
month = {2},
number = {4},
pages = {443-470},
publisher = {EDP Sciences},
title = {Sturmian jungle (or garden?) on multiliteral alphabets},
url = {http://eudml.org/doc/193070},
volume = {44},
year = {2011},
}

TY - JOUR
AU - Balková, L'ubomíra
AU - Pelantová, Edita
AU - Starosta, Štěpán
TI - Sturmian jungle (or garden?) on multiliteral alphabets
JO - RAIRO - Theoretical Informatics and Applications
DA - 2011/2//
PB - EDP Sciences
VL - 44
IS - 4
SP - 443
EP - 470
AB - The properties characterizing Sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of Sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of Sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions of Sturmian words.
LA - eng
KW - Sturmian words; generalizations of Sturmian words; palindromes; rich words; rich words
UR - http://eudml.org/doc/193070
ER -

References

top
  1. B. Adamczewski, Codages de rotations et phénomènes d'autosimilarité. J. Théor. Nombres Bordeaux14 (2002) 351–386.  
  2. B. Adamczewski, Balances for fixed points of primitive substitutions. Theoret. Comput. Sci.307 (2003) 47–75.  
  3. J.P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci.292 (2003) 9–31.  
  4. P. Ambrož, Ch. Frougny, Z. Masáková and E. Pelantová, Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier56 (2006) 2131–2160.  
  5. P. Arnoux, C. Mauduit, I. Shiokawa and J.-I. Tamura, Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France122 (1994) 1–12.  
  6. P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215.  
  7. P. Baláži, Z. Masáková and E. Pelantová, Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci.380 (2007) 266–275.  
  8. L'. Balková, E. Pelantová and &Aring;. Starosta, Palindromes in infinite ternary words. RAIRO-Theor. Inf. Appl.43 (2009) 687–702.  
  9. L'. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words. Monatsh. Math.155 (2008) 251–263.  
  10. L'. Balková, E. Pelantová and O. Turek, Combinatorial and arithmetical properties of infinite words associated with quadratic non-simple Parry numbers. RAIRO-Theor. Inf. Appl.41 (2007) 307–328.  
  11. Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Commun. Math. Phys.174 (1995) 43–56.  
  12. J. Berstel, Recent results on extensions of Sturmian words. Int. J. Algebra Comput.12 (2002) 371–385.  
  13. J. Berstel, L. Boasson, O. Carton and I. Fagnot, Infinite words without palindromes. arXiv:0903.2382 (2009), in Proc. CoRR 2009.  
  14. J.P. Borel, Complexity and palindromic complexity of billiards words, in Proceedings of WORDS 2005, edited by S. Brlek, C. Reutenauer (2005) 175–183.  
  15. S. Brlek, S. Hamel, M. Nivat and C. Reutenauer, On the palindromic complexity of infinite words. Int. J. Found. Comput. Sci.2 (2004) 293–306.  
  16. M. Bucci, A. De Luca, A. Glen and L.Q. Zamboni, A connection between palindromic and factor complexity using return words. Adv. Appl. Math.42 (2009) 60–74.  
  17. M. Bucci, A. De Luca, A. Glen and L.Q. Zamboni, A new characteristic property of rich words. Theoret. Comput. Sci.410 (2009) 2860–2863.  
  18. J. Cassaigne, Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 41 (1997) 67–88.  
  19. J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier50 (2000) 1265–1276.  
  20. E.M. Coven and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theor.7 (1973) 138–153.  
  21. J. Currie and N. Rampersad, Recurrent words with constant Abelian complexity. Adv. Appl. Math. (2010) DOI:  DOI10.1016/j.aam.2010.05.001
  22. X. Droubay and G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci.223 (1999) 73–85.  
  23. X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci.255 (2001) 539–553.  
  24. F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998) 89–101.  
  25. I. Fagnot and L. Vuillon, Generalized balances in Sturmian words. Discrete Appl. Math.121 (2002) 83–101.  
  26. S. Ferenczi, Les transformations de Chacon: combinatoire, structure géométrique, lien avec les systèmes de complexité 2n + 1. Bull. Soc. Math. France123 (1995) 271–292.  
  27. S. Ferenczi and L. Zamboni, Languages of k-interval exchange transformations. Bull. Lond. Math. Soc.40 (2008) 705–714.  
  28. C. Frougny, Z. Masáková and E. Pelantová, Complexity of infinite words associated with beta-expansions. RAIRO-Theor. Inf. Appl.38 (2004) 162–184.  
  29. A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl.43 (2009) 403–442.  
  30. A. Glen, J. Justin, S. Widmer and L.Q. Zamboni, Palindromic richness. Eur. J. Comb.30 (2009) 510–531.  
  31. A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schröodinger operators. Commun. Math. Phys.174 (1995) 149–159.  
  32. C. Holton and L.Q. Zamboni, Geometric realizations of substitutions. Bull. Soc. Math. France126 (1998) 149–179.  
  33. J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci.276 (2002) 281–313.  
  34. J. Justin and L. Vuillon, Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl.34 (2000) 343–356.  
  35. M.S. Keane, Interval exchange transformations. Math. Z.141 (1975) 25–31.  
  36. M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press (2002).  
  37. Z. Masáková, E. Pelantová, Relation between powers of factors and the recurrence function characterizing Sturmian words. Theoret. Comput. Sci.410 (2009) 3589–3596.  
  38. M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866.  
  39. M. Morse and G.A. Hedlund, Symbolic dynamics II - Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.  
  40. G. Rauzy, Échanges d'intervalles et transformations induites. Acta Arith.34 (1979) 315–328.  
  41. G. Richomme, Another characterization of Sturmian words (one more). Bull. Eur. Assoc. Theor. Comput. Sci. EATCS67 (1999) 173–175.  
  42. G. Richomme, K. Saari and L.Q. Zamboni, Abelian complexity of minimal subshifts. J. London Math. Soc. (2010) DOI:  DOI10.1112/jlms/jdq063
  43. G. Richomme, K. Saari and L.Q. Zamboni, Balance and abelian complexity of the Tribonacci word. Adv. Appl. Math.45 (2010) 212–231.  
  44. G. Rote, Sequences with subword complexity 2n. J. Number Theory46 (1993) 196–213.  
  45. J. Smillie and C. Ulcigrai, Beyond Sturmian sequences: coding linear trajectories in the regular octagon. Proc. London Math. Soc. (2010) DOI:  DOI10.1112/plms/pdq018
  46. S. Tabachnikov, Billiards. Panoramas et synthèse, SMF, Numéro 1 (1995).  
  47. O. Turek, Balances and Abelian complexity of a certain class of infinite ternary words. RAIRO-Theor. Inf. Appl.44 (2010) 317–341.  
  48. O. Turek, Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers. RAIRO-Theor. Inf. Appl.41 (2007) 123–135.  
  49. L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Comb.22 (2001) 263–275.  
  50. L. Vuillon, Balanced words. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 787–805.  
  51. L. Vuillon, On the number of return words in infinite words with complexity 2n + 1. LIAFA Research Report (2000).  

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.