Look and Say Fibonacci

Séébold, Patrice

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 729-746 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

The $L S$ (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, $L S (1 1 2 3 3) = 2 1 1 2 2 3$ (two $1$ , one $2$ , two $3$ ). We start the study of the behaviour of binary words generated by morphisms under the $L S$ operator, focusing in particular on the Fibonacci word.

Publié le : 2008-01-01

MR 2458704 | Zbl 1155.68071

DOI : https://doi.org/10.1051/ita:2007060
Classification: 68R15

@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},
     volume = {42},
     year = {2008},
     pages = {729-746},
     doi = {10.1051/ita:2007060},
     mrnumber = {2458704},
     zbl = {1155.68071},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_4_729_0}
}

Séébold, Patrice. Look and Say Fibonacci. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 729-746. doi : 10.1051/ita:2007060. http://gdmltest.u-ga.fr/item/ITA_2008__42_4_729_0/

Bibliographie

[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