Look and Say Fibonacci
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 42 (2008) no. 4, p. 729-746

The LS (Look and Say) derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, LS(11233)=211223 (two 1, one 2, two 3). We start the study of the behaviour of binary words generated by morphisms under the LS operator, focusing in particular on the Fibonacci word.

DOI : https://doi.org/10.1051/ita:2007060
Classification:  68R15
Keywords: look and say sequence, Conway, binary words, Fibonacci word, morphisms, Lyndon factorization
@article{ITA_2008__42_4_729_0,
     author = {S\'e\'ebold, Patrice},
     title = {Look and Say Fibonacci},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {4},
     year = {2008},
     pages = {729-746},
     doi = {10.1051/ita:2007060},
     zbl = {1155.68071},
     mrnumber = {2458704},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2008__42_4_729_0}
}
Séébold, Patrice. Look and Say Fibonacci. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 42 (2008) no. 4, pp. 729-746. doi : 10.1051/ita:2007060. http://www.numdam.org/item/ITA_2008__42_4_729_0/

[1] J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations. Cambridge University Press (2003). | MR 1997038 | Zbl 1086.11015

[2] S. Arshon, Démonstration de l'existence de suites asymétriques infinies. Mat. Sb. 44 (1937) 769-777 (in Russian), 777-779 (French summary). | JFM 63.0928.01 | Zbl 0018.11503

[3] J. Berstel, Mots sans carré et morphismes itérés. Discrete Math. 29 (1980). 235-244. | MR 560766 | Zbl 0444.20050

[4] J. Berstel, Fibonacci words - a survey1986) 13-27. | Zbl 0589.68053

[5] J. Berstel and P. Séébold, A characterization of Sturmian morphisms, MFCS'93, Gdansk (Poland). Lect. Notes Comput. Sci. 711 (1993) 281-290. | MR 1265070 | Zbl 0925.11026

[6] J. Berstel and P. Séébold, A remark on morphic Sturmian words. RAIRO-Theor. Inf. Appl. 28 (1994) 255-263. | Numdam | MR 1282447 | Zbl 0883.68104

[7] S. Brlek, S. Dulucq, A. Ladouceur and L. Vuillon, Combinatorial properties of smooth infinite words. Theor. Comput. Sci. 352 (2006) 306-317. | MR 2207527 | Zbl 1116.11014

[8] A. Cobham, Uniform tag sequences. Math. Syst. Theory 6 (1972) 164-192. | MR 457011 | Zbl 0253.02029

[9] J.H. Conway, The weird and wonderful chemistry of audioactive decay, in Open problems in communication and computation, edited by T.M. Cover, B. Gopinath. Springer-Verlag, New-York (1987) 173-188. See also Eureka 46 (1986) 5-18. | MR 922073

[10] B. Germain-Bonne, À propos d'une itération sur chaînes de caractères numériques. Laboratoire d'Analyse Numérique et d'Optimisation. Université Lille 1, Research Report ANO 293 (1993).

[11] B. Germain-Bonne, Chaînes alphanumériques ; cycles et points fixes. Laboratoire d'Analyse Numérique et d'Optimisation. Université Lille 1, Research Report ANO 301 (1993).

[12] B. Germain-Bonne, Mots autodescriptifs et co-descriptifs. Laboratoire d'Analyse Numérique et d'Optimisation. Université Lille 1, Research Report ANO 332 (1994).

[13] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and Applications, Vol. 17. Addison-Wesley, Reading, Mass. (1983). Reprinted in the Cambridge Mathematical Library, Cambridge University Press (1997). | MR 1475463 | Zbl 0514.20045

[14] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press (2002). | MR 1905123 | Zbl 1001.68093

[15] G. Melançon, Lyndon factorization of sturmian words. Discrete Math. 210 (2000) 137-149. | MR 1731611 | Zbl 0946.68113

[16] J.-J. Pansiot, Hiérarchie et fermeture de certaines classes de tag-systèmes. Acta Informatica 20 (1983) 179-196. | MR 727164 | Zbl 0507.68046

[17] G. Richomme, On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci. 9 (2007) 89-108. | MR 2306522 | Zbl 1152.68490

[18] Handbook of Formal Languages, Vol. 1, edited by G. Rozenberg, A. Salomaa. Springer (1997). | MR 1469992 | Zbl 0866.68057

[19] P. Séébold, On the conjugation of standard morphisms. Theor. Comput. Sci. 195 (1998) 91-109. | MR 1603835 | Zbl 0981.68104

[20] P. Séébold, About some overlap-free morphisms on a n-letter alphabet. J. Autom. Lang. Comb. 7 (2002) 579-597. | MR 1990460 | Zbl 1095.68090

[21] R. Siromoney, L. Mathew, V.R. Dare and K.G. Subramanian, Infinite Lyndon words. Inform. Process Lett. 50 (1994) 101-104. | MR 1281048 | Zbl 0803.68093