×

Palindromes and Sturmian words. (English) Zbl 0930.68116

Summary: An infinite word \(x\) over the alphabet \(A\) is Sturmian if and only if \(g_{x}(n)=n+1\) for any integer \(n\), where \(g_{x}(n)\) is the number of distinct words of length \(n\) occurring in \(x\). A palindrome is a word that can be read indistinctly from left to right or from right to left. We prove that \(x\) is Sturmian if and only if \(h_{x}(n)=1+(n \bmod 2)\) for any integer \(n\), where \(h_{x}(n)\) is the number of palindromes of length n occurring in \(x\). An infinite word \(x\) over the alphabet \(A\) is generated by a morphism \(f\) if there exists a letter \(c\in A\) such that \(\lim_{n\rightarrow \infty}f^{n}(c)=x\). We prove the existence of a morphism that generates the palindromes of any infinite Sturmian word generated by a morphism.

MSC:

68R15 Combinatorics on words
11B85 Automata sequences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J. P., Sur la complexité des suites infinies, Bull. Belgian Math. Soc., 1, 133-143 (1994) · Zbl 0803.68094
[2] Berstel, J., Recent results in Sturmian words, (Dassaw, J., Proc. 2nd Internat. Conf. Developments in Language Theory (1995), World Scientific: World Scientific Singapore) · Zbl 1096.68689
[3] Berstel, J.; de Luca, A., Sturmian words, Lyndon words and trees, Theoret. Comput. Sci., 178, 1-2, 171-203 (1997) · Zbl 0901.68155
[4] Berstel, J.; Séébold, P., A characterization of Sturmian morphisms, (Borzyskovski, A.; Sokolovski, S., Proc. 21st Internat. Symp. on MFCS. Proc. 21st Internat. Symp. on MFCS, Lecture Notes Computer Science, vol. 711 (1993), Springer: Springer Berlin), 281-290 · Zbl 0925.11026
[5] Berstel, J.; Séébold, P., A remark on morphic Sturmian words, Theoret. Inform. Appl., 28, 255-263 (1994) · Zbl 0883.68104
[6] Brown, T. C., Descriptions of the characteristic sequence of an irrational, Canad. Math. Bull., 36, 15-21 (1993) · Zbl 0804.11021
[7] Chuan, W.-F., Symmetric Fibonacci words, Fibonacci Quart., 31, 251-255 (1993) · Zbl 0776.68098
[8] Coven, E.; Hedlund, G. A., Sequences with minimal block growth, Math. System Theory, 7, 138-153 (1973) · Zbl 0256.54028
[9] Crisp, D.; Moran, W.; Pollington, A.; Shiue, P., Substitution invariant cutting sequences, J. de Théorie des Nombres de Bordeaux, 5, 123-138 (1993) · Zbl 0786.11041
[10] Culik, K.; Kharumäki, J., Iterative devices generating infinite words, Internat. J. Algebra Comput., 5, 69-97 (1994)
[11] de Luca, A., A combinatorial property of the Fibonacci words, Inform. Process. Lett., 12, 193-195 (1981) · Zbl 0468.20049
[12] de Luca, A., On Standard Sturmian morphisms, Theoret. Comput. Sci., 178, 1-2, 205-224 (1997) · Zbl 0901.68154
[13] A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci., to appear.; A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci., to appear. · Zbl 0911.68098
[14] de Luca, A.; Mignosi, F., Some combinatorial properties of Sturmian words, Theoret. Comput. Sci., 136, 361-385 (1994) · Zbl 0874.68245
[15] Droubay, X., Palindromes in the Fibonacci word, Inform. Process. Lett., 55, 217-221 (1995) · Zbl 1004.68537
[16] Dulucq, S.; Gouyou-Beauchamps, D., Sur les facteurs des suites de Sturm, Theoret. Comput. Sci., 71, 381-400 (1990) · Zbl 0694.68048
[17] Hedlund, G. A., Sturmian minimal sets, Amer. J. Math., 66, 605-620 (1944) · Zbl 0063.01982
[18] Hedlund, G. A.; Morse, M., Symbolic dynamics II: Sturmian sequences, Amer. J. Math., 61, 1-42 (1940) · JFM 66.0188.03
[19] J. Justin, G. Pirillo, Decimations and Sturmian words, Rapport interne de l’Institut Gaspard Monge, 97-07.; J. Justin, G. Pirillo, Decimations and Sturmian words, Rapport interne de l’Institut Gaspard Monge, 97-07.
[20] Justin, J.; Pirillo, G., On a combinatorial property of Sturmian words, Theoret. Comput. Sci., 154, 387-394 (1996) · Zbl 0872.68144
[21] Lothaire, M., Combinatorics on words, (Encyclopedia of Mathematics and its Applications, vol. 17 (1983), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 1001.68093
[22] Markoff, A. A., Sur une question de Jean Bernoulli, Math. Ann., 19, 27-36 (1882) · JFM 13.0313.01
[23] Mignosi, F., Infinite words with linear subword complexity, Theoret. Comput. Sci., 65, 221-242 (1989) · Zbl 0682.68083
[24] Mignosi, F.; Séébold, P., Morphismes Sturmiens et rg̀les de Rauzy, J. de Théorie des Nombres de Bordeaux, 5, 221-233 (1993) · Zbl 0797.11029
[25] Pirillo, G., Some remarks on the Fibonacci word (1995), Research Institute for Mathematical Sciences: Research Institute for Mathematical Sciences Kyoto · Zbl 0939.20504
[26] G. Pirillo, Fibonacci Numbers and words, Actes du Séminaire Lotharingien de Combinatoire, vol. 30, Discrete Mathematics, to appear.; G. Pirillo, Fibonacci Numbers and words, Actes du Séminaire Lotharingien de Combinatoire, vol. 30, Discrete Mathematics, to appear. · Zbl 0882.68113
[27] Rauzy, G., Mots infinis en arithmétique, (Nivat, M.; Perrin, D., Automata on Infinite Words. Automata on Infinite Words, Lecture Notes in Computer Science, vol. 192 (1984), Springer: Springer Berlin), 165-171 · Zbl 0613.10044
[28] Séébold, P., Fibonacci morphisms and Sturmian words, Theoret. Comput. Sci., 88, 365-384 (1991) · Zbl 0737.68068
[29] Séébold, P., On the conjugation of Standard morphisms, (Penczek, W.; Szalas, A., Proc. 18st Internat. Symp. MFCS. Proc. 18st Internat. Symp. MFCS, Lecture Notes in Computer Science, vol. 1113 (1996), Springer: Springer Berlin), 506-516 · Zbl 0889.68094
[30] Venkov, B. A., Elementary Number Theory (1970), Wolters-Noordhoff: Wolters-Noordhoff Groningen · Zbl 0204.37101
[31] Wen, Z.-X.; Wen, Z.-Y, Local isomorphisms of invertible substitutions, Comptes rendus de l’Académie des Sciences, 318, 299-304 (1994) · Zbl 0812.11018
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.