×
Justin, Jacques; Pirillo, Giuseppe

Episturmian words and episturmian morphisms. (English) Zbl 1002.68116

Theor. Comput. Sci. 276, No. 1-2, 281-313 (2002).
Summary: Infinite episturmian words are a generalization of Sturmian words which includes the Arnoux-Rauzy sequences. We continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. Palindromic and periodic factors of these words are described. We consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of Sturmian words. Finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.

Cited in 67 Documents

MSC:

68R15 Combinatorics on words

Keywords:

episturmian word; Arnoux-Rauzy sequence; fractional power; palindrome; intercept
PDF BibTeX XML Cite
\textit{J. Justin} and \textit{G. Pirillo}, Theor. Comput. Sci. 276, No. 1--2, 281--313 (2002; Zbl 1002.68116)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

Online Encyclopedia of Integer Sequences:

Fixed under the morphism 1 -> 132, 2 -> 1, 3 -> 3, starting with 31.

References:

[1] Alessandri, P.; Berthé, V., Three distance theorems and combinatorics on words, Enseign. math., 44, 1-2, 103-132, (1998) · Zbl 0997.11051
[2] Allouche, J.-P., Sur la complexité des suites infinies, Bull. belg. math. soc., 1, 133-143, (1994) · Zbl 0803.68094
[3] P. Arnoux, personal communication, 2000.
[4] P. Arnoux, S. Ito, Pisot substitutions and Rauzy fractal, preprint IML 1998-18, Bull. Belg. Math. Soc., to appear. · Zbl 1007.37001
[5] Arnoux, P.; Mauduit, C., Complexité des suites engendrées par des récurrences unipotentes, Acta arith., 76, 1, 85-97, (1996) · Zbl 0860.68082
[6] Arnoux, P.; Rauzy, G., Représentation géometrique de suites de complexité \(2n+1\), Bull. soc. math. France, 119, 199-215, (1991) · Zbl 0789.28011
[7] Baryshnikov, Yu., Complexity of trajectories in rectangular billiards, Comm. math. phys., 174, 43-56, (1995) · Zbl 0839.11006
[8] Berstel, J., Recent results in Sturmian words, (), 13-24 · Zbl 1096.68689
[9] V. Canterini, Géométrie des substitutions Pisot unitaires, Thèse Fac. Sci. de Luminy (2000).
[10] Cassaigne, J.; Ferenczi, S.; Zamboni, L.Q., Imbalances in arnoux – rauzy sequences, Ann. inst. Fourier, Grenoble, 50, 1265-1276, (2000) · Zbl 1004.37008
[11] Castelli, G.; Mignosi, F.; Restivo, A., Fine and Wilf’s theorem for three periods and a generalization of Sturmian words, Theoret. comput. sci., 218, 83-94, (1999) · Zbl 0916.68114
[12] N. Chekhova, P. Hubert, A. Messaoudi, Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci, preprint IML 1998-24, J. Théor. Nombres Bordeaux, to appear. · Zbl 1038.37010
[13] Crisp, D.; Moran, W.; Pollington, A.; Shiue, P., Substitution invariant cutting sequences, J. théor. nombres Bordeaux, 5, 123-137, (1993) · Zbl 0786.11041
[14] De Luca, A., Sturmian wordsstructure, combinatorics and their arithmetics, Theoret. comput. sci., 183, 45-82, (1997) · Zbl 0911.68098
[15] Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de luca and Rauzy, Theoret. comput. sci., 255, 1-2, 539-553, (2001) · Zbl 0981.68126
[16] Droubay, X.; Pirillo, G., Palindromes and Sturmian words, Theoret. comput. sci., 223, 1-2, 73-85, (1999) · Zbl 0930.68116
[17] Justin, J., On a paper by castelli, mignosi, restivo, RAIRO inform. théor. appl., 34, 373-377, (2000) · Zbl 0987.68056
[18] Justin, J.; Pirillo, G., Decimations and Sturmian words, RAIRO inform. théor. appl., 31, 271-290, (1997) · Zbl 0889.68090
[19] Justin, J.; Pirillo, G., Fractional powers in Sturmian words, Theoret. comput. sci., 255, 1-2, 363-376, (2001) · Zbl 0974.68159
[20] Justin, J.; Vuillon, L., Return words in sturmian and Episturmian words, RAIRO inform. théor. appl., 34, 343-356, (2000) · Zbl 0987.68055
[21] M. Lothaire, Algebraic Combinatorics on Words, Preliminary Version, February 16, 1999, Institut Gaspard Monge, Univ. Marne-la-Vallée. · Zbl 1001.68093
[22] Mignosi, F.; Pirillo, G., Repetitions in the Fibonacci infinite word, RAIRO inform. théor. appl., 26, 199-204, (1992) · Zbl 0761.68078
[23] Mignosi, F.; Séébold, P., Morphismes sturmiens et règles de Rauzy, J. théor. nombres Bordeaux, 5, 221-233, (1993) · Zbl 0797.11029
[24] Morse, M.; Hedlund, G.A., Symbolic dynamics II: Sturmian trajectories, Amer. J. math., 62, 1-42, (1940) · JFM 66.0188.03
[25] Parvaix, B., Proprietés d’invariance des mots sturmiens, J. théor. nombres Bordeaux, 9, 351-369, (1997) · Zbl 0904.11008
[26] Queffélec, M., Substitution dynamical systems, spectral analysis, Lecture notes in mathematics, vol. 1294, (1987), Springer Berlin
[27] Rauzy, G., Nombres algébriques et substitutions, Bull. soc. math. France, 110, 147-178, (1982) · Zbl 0522.10032
[28] G. Rauzy, Suites à termes dans un alphabet fini, Séminaire de Théorie des nombres de Bordeaux, 1982-1983, pp. 25-01-25-16.
[29] Rauzy, G., Mots infinis en arithmétique, (), 165-171 · Zbl 0613.10044
[30] Risley, R.N.; Zamboni, L.Q., A generalization of Sturmian sequences, combinatorial structure and transcendence, Acta arith., 95, 167-184, (2000) · Zbl 0953.11007
[31] Tijdeman, R., On the minimal complexity of infinite words, Indag. math., N.S. 10, 1, 123-129, (1999) · Zbl 1027.11018
[32] Vandeth, D., Sturmian words and words with a critical exponent, Theoret. comput. sci., 242, 283-300, (2000) · Zbl 0944.68148
[33] Wozny, N.N.; Zamboni, L.Q., Frequencies of factors in arnoux – rauzy sequences, Acta arith., 96, 261-278, (2001) · Zbl 0973.11030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.