×

The numbers of repeated palindromes in the Fibonacci and Tribonacci words. (English) Zbl 1380.68321

The Fibonacci word \(F\) is the fixed point beginning with \(a\) of the morphism \(\sigma(a)=ab\) and \(\sigma(b)=a\). Similarly, the Tribonacci word \(T\) is the fixed point beginning with \(a\) of the morphism \(\tau(a)=ab\), \(\tau(b)=ac\) and \(\tau(c)=a\). Let \(F[1, n]\) (resp. \(T[1, n]\)) be the prefix of \(F\) (resp. \(T\)) of length \(n\). A palindrome is a finite word that reads the same backwards as forwards.
From previous studies the number of distinct palindromes in \(F[1, n]\) (resp. \(T[1, n]\)) is \(n + 1\) for all \(n\). In the present paper the authors consider the numbers of repeated palindromes in \(F[1, n]\) and \(T[1, n]\). Using the “gap sequence” properties of \(F\) and \(T\), which were introduced and studied by the same authors, they determine the positions of all occurrences for all palindromes, give an algorithm for counting the number of repeated palindromes in \(F[1, n]\) and \(T[1, n]\), and also get explicit expressions for some special \(n\).
The research on counting the repeated palindromes is not rich. To the best of our knowledge it seems that the authors are the first to study this problem on the Fibonacci and Tribonacci words. The paper’s approach for counting the repeated palindromes seems suitable for the \(m\)-bonacci word, and even suitable for Sturmian sequences, episturmian sequences etc., if the “gap sequence” properties of them are found.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J. P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1086.11015
[2] Chuan, W.-F., Symmetric Fibonacci words, Fibonacci Quart., 3, 251-255 (1993) · Zbl 0776.68098
[3] Droubay, X., Palindromes in the Fibonacci word, Inform. Process. Lett., 55, 217-221 (1995) · Zbl 1004.68537
[4] Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci., 255, 539-553 (2001) · Zbl 0981.68126
[5] Durand, F., A characterization of substitutive sequences using return words, Discrete Math., 179, 89-101 (1998) · Zbl 0895.68087
[6] Fraenkel, A. S.; Simpson, J., The exact number of squares in Fibonacci words, Theoret. Comput. Sci., 218, 95-106 (1999) · Zbl 0916.68122
[7] Fraenkel, A. S.; Simpson, J., Corrigendum to “The exact number of squares in Fibonacci words”, Theoret. Comput. Sci., 547, 122 (2014) · Zbl 1303.68098
[9] Huang, Y.-K.; Wen, Z.-Y., The sequence of return words of the Fibonacci sequence, Theoret. Comput. Sci., 593, 106-116 (2015) · Zbl 1330.68236
[10] Huang, Y.-K.; Wen, Z.-Y., Kernel words and gap sequence of the Tribonacci sequence, Acta Math. Sci. Ser. B Engl. Ed., 36, 1, 173-194 (2016) · Zbl 1363.11045
[11] Iliopoulos, C. S.; Moore, D.; Smyth, W. F., A characterization of the squares in a Fibonacci string, Theoret. Comput. Sci., 172, 281-291 (1997) · Zbl 0903.68050
[12] Karhumaki, J., On cube-free \(\omega \)-words generated by binary morphism, Discrete Appl. Math., 5, 279-297 (1983) · Zbl 0505.03022
[13] Krieger, D., Critical exponents and stabilizers of infinite words, Theoret. Comput. Sci., 400, 1-3, 169-181 (2008) · Zbl 1145.68042
[14] Mignosi, F.; Pirillo, G., Repetitions in the Fibonacci infinite word, RAIRO Theor. Inform. Appl., 26, 3, 199-204 (1992) · Zbl 0761.68078
[15] Mousavi, H.; Schaeffer, L.; Shallit, J., Decision algorithms for Fibonacci-automatic words, I: Basic results, RAIRO Theor. Inform. Appl., 50, 1, 39-66 (2016) · Zbl 1366.68226
[16] Mousavi, H.; Shallit, J., Mechanical proofs of properties of the Tribonacci word, (Combinatorics on Words (2014), Springer International Publishing), 170-190 · Zbl 1350.68218
[17] Rytter, W., The structure of subword graphs and suffix trees in Fibonacci words, Theoret. Comput. Sci., 363, 2, 211-223 (2006) · Zbl 1153.68044
[18] Tan, B.; Wen, Z.-Y., Some properties of the Tribonacci sequence, European J. Combin., 28, 1703-1719 (2007) · Zbl 1120.11009
[19] Wen, Z.-X.; Wen, Z.-Y., Some properties of the singular words of the Fibonacci word, European J. Combin., 15, 587-598 (1994) · Zbl 0823.68087
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.