[en] We introduce a variation of the Ziv–Lempel and Crochemore factorizations of words by requiring each factor to be a palindrome. We compute these factorizations for the Fibonacci word, and more generally, for all m-bonacci words.
Disciplines :
Mathematics
Author, co-author :
Jahannia, Marieh; University of Tehran > School of Mathematics, Statistics and Computer Science, College of Science
Mohammad-noori, Morteza; University of Tehran > School of Mathematics, Statistics and Computer Science, College of Science
Rampersad, Narad; University of Winnipeg > Department of Mathematics and Statistics
Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Palindromic Ziv–Lempel and Crochemore Factorizations of m-Bonacci Infinite Words
Allouche, J.-P., Baake, M., Cassaigne, J., Damanik, D., Palindrome complexity. Theor. Comput. Sci. 292 (2003), 9–31.
Berstel, J., Savelli, A., Crochemore factorization of Sturmian and other infinite words. Proc. MFCS'06 LNCS, vol. 4162, 2006, Springer, 157–166.
Constantinescu, S., Ilie, L., The Lempel–Ziv complexity of fixed points of morphisms. SIAM J. Discrete Math. 21 (2007), 466–481.
Crochemore, M., Recherche linéaire d'un carré dans un mot. C. R. Math. Acad. Sci. Paris 296 (1983), 781–784.
Fici, G., Factorizations of the Fibonacci infinite word. J. Integer Seq., 18(9), 2015, 15.9.3.
Ghareghani, N., Mohammad–Noori, M., Sharifani, P., On z-factorization and c-factorization of standard episturmian words. Theor. Comput. Sci. 412 (2011), 5232–5238.
Glen, A., On Sturmian and Episturmian Words, and Related Topics. Ph.D. Thesis, 2006.
Justin, J., Pirillo, G., Episturmian words and episturmian morphisms. Theor. Comput. Sci. 276:1–2 (2002), 281–313.
Lempel, A., Ziv, J., On the complexity of finite sequences. IEEE Trans. Inf. Theory IT-22 (1976), 75–81.
Lothaire, M., Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 90, 2002, Cambridge University Press.
Melançon, Guy, Lyndon words and singular factors of Sturmian words. Theor. Comput. Sci. 218 (1999), 41–59.
Tan, B., Wen, Z.-Y., Some properties of the Tribonacci sequence. Eur. J. Comb. 28:6 (2007), 1703–1719.
Wen, Z.-X., Wen, Z.-Y., Some properties of the singular words of the Fibonacci word. Eur. J. Comb. 15 (1994), 587–598.
