In this paper, we define the notion of maximal suffix duplication and the notion of strict square completion of maximal suffix in an infinite word. Then, we get that each of these operations can be used iteratively to generate the Fibonacci word F. Finally, we show that duplication generates F faster than strict square completion.

morphism, duplication, strict completion, maximal square, Fibonacci word.

Received: February 3, 2023; Accepted: March 20, 2023; Published: May 20, 2023

How to cite this article: K. Ernest Bognini, Idrissa Kaboré and B. Thomas Ouedraogo, Square completion operation of maximal suffix in Fibonacci word, Advances and Applications in Discrete Mathematics 39(1) (2023), 99-115. http://dx.doi.org/10.17654/0974165823039

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] F. Dejean, Sur un théorème de Thue, J. Combin. Theory Ser. A 13 (1972), 90-99 (in French).
[2] M. Dumitran, J. Gil, F. Manea and V. Mitrana, Bounded prefix suffix duplication, M. Holzer, eds., CIAA 2014, LNCS, 8587, Springer, Heidelberg, 2014, pp. 176-187.
[3] M. Dumitran and F. Manea, Prefix-suffix square completion, LNCS 9304, 2015, pp. 147-159.
[4] L. J. Garcia, F. Manea and V. Mitrana, Prefix-suffix duplication, J. Comput. Syst. Sci. 80(7) (2014), 1254-1265.
[5] M. Hall, Generators and relation in groups - the Burnside problem, Lectures on Modern Mathematics, Vol. 2, Wiley, New York, 1964, pp. 42-92.
[6] J. Knuth, D. E. Morris and J. H. Pratt, Fast pattern matching in strings, SIAM J. Comput. 6(2) (1977), 323-350.
[7] R. Kolpakov and G. Kucherov, Finding maximal repetitions in a word in linear time, Proceedings of FOCS, 1999, pp. 596-604.
[8] M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics, Addison-Wesley, Cambridge University Press, Vol. 17, 2002.
[9] P. Séébold, Propriétés combinatoires des mots infinis engendrés par certains morphismes, Thèse de Doctorat, Tec. LITP., 1985, pp. 85-114.
[10] A. Thue, Selected Mathematical Papers, T. Nagell, A. Selberg, S. Selberg and K. Thalberg, eds., Universitetsforlaget, Oslo, 1977.