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.  Zbl1059.68083
  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.  Zbl1121.68089
  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.  Zbl0791.58034
  6. P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215.  Zbl0789.28011
  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.  Zbl1119.68137
  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.  Zbl1185.68503
  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.  Zbl1144.11009
  11. Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Commun. Math. Phys.174 (1995) 43–56.  Zbl0839.11006
  12. J. Berstel, Recent results on extensions of Sturmian words. Int. J. Algebra Comput.12 (2002) 371–385.  Zbl1007.68141
  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.  Zbl1067.68113
  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.  Zbl1160.68027
  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.  Zbl1173.68048
  18. J. Cassaigne, Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 41 (1997) 67–88.  Zbl0921.68065
  19. J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier50 (2000) 1265–1276.  Zbl1004.37008
  20. E.M. Coven and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theor.7 (1973) 138–153.  Zbl0256.54028
  21. J. Currie and N. Rampersad, Recurrent words with constant Abelian complexity. Adv. Appl. Math. (2010) DOI:  Zbl1222.68126DOI10.1016/j.aam.2010.05.001
  22. X. Droubay and G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci.223 (1999) 73–85.  Zbl0930.68116
  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.  Zbl0981.68126
  24. F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998) 89–101.  Zbl0895.68087
  25. I. Fagnot and L. Vuillon, Generalized balances in Sturmian words. Discrete Appl. Math.121 (2002) 83–101.  Zbl1002.68117
  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.  Zbl1147.37008
  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.  Zbl1104.11013
  29. A. Glen and J. Justin, Episturmian words: a survey. RAIRO-Theor. Inf. Appl.43 (2009) 403–442.  Zbl1182.68155
  30. A. Glen, J. Justin, S. Widmer and L.Q. Zamboni, Palindromic richness. Eur. J. Comb.30 (2009) 510–531.  Zbl1169.68040
  31. A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schröodinger operators. Commun. Math. Phys.174 (1995) 149–159.  Zbl0839.11009
  32. C. Holton and L.Q. Zamboni, Geometric realizations of substitutions. Bull. Soc. Math. France126 (1998) 149–179.  Zbl0931.11004
  33. J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci.276 (2002) 281–313.  Zbl1002.68116
  34. J. Justin and L. Vuillon, Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl.34 (2000) 343–356.  Zbl0987.68055
  35. M.S. Keane, Interval exchange transformations. Math. Z.141 (1975) 25–31.  Zbl0278.28010
  36. M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press (2002).  Zbl1001.68093
  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.  Zbl1171.68036
  38. M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866.  Zbl0019.33502
  39. M. Morse and G.A. Hedlund, Symbolic dynamics II - Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.  Zbl0022.34003
  40. G. Rauzy, Échanges d'intervalles et transformations induites. Acta Arith.34 (1979) 315–328.  Zbl0414.28018
  41. G. Richomme, Another characterization of Sturmian words (one more). Bull. Eur. Assoc. Theor. Comput. Sci. EATCS67 (1999) 173–175.  Zbl0942.11021
  42. G. Richomme, K. Saari and L.Q. Zamboni, Abelian complexity of minimal subshifts. J. London Math. Soc. (2010) DOI:  Zbl1211.68300DOI10.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.  Zbl1203.68131
  44. G. Rote, Sequences with subword complexity 2n. J. Number Theory46 (1993) 196–213.  Zbl0804.11023
  45. J. Smillie and C. Ulcigrai, Beyond Sturmian sequences: coding linear trajectories in the regular octagon. Proc. London Math. Soc. (2010) DOI:  Zbl1230.37021DOI10.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.  Zbl1146.68410
  49. L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Comb.22 (2001) 263–275.  Zbl0968.68124
  50. L. Vuillon, Balanced words. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 787–805.  Zbl1070.68129
  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.