Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T23:07:27.022Z Has data issue: false hasContentIssue false
  • English
  • Français

Sturmian jungle (or garden?) on multiliteral alphabets

Published online by Cambridge University Press:  28 February 2011

L'ubomíra Balková ,
Edita Pelantová  and
Štěpán Starosta
L'ubomíra Balková
Affiliation:
Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, 120 00 Praha 2, Czech Republic; [email protected]; [email protected]; [email protected]
Edita Pelantová
Affiliation:
Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, 120 00 Praha 2, Czech Republic; [email protected]; [email protected]; [email protected]
Štěpán Starosta
Affiliation:
Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, 120 00 Praha 2, Czech Republic; [email protected]; [email protected]; [email protected]
Get access

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.

Keywords

Sturmian wordsgeneralizations of Sturmian wordspalindromesrich words
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 4 , October 2010 , pp. 443 - 470
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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