Look and Say Fibonacci
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 42 (2008) no. 4, pp. 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\left(1\phantom{\rule{0.222222em}{0ex}}1\phantom{\rule{0.222222em}{0ex}}2\phantom{\rule{0.222222em}{0ex}}3\phantom{\rule{0.222222em}{0ex}}3\right)=2\phantom{\rule{0.222222em}{0ex}}1\phantom{\rule{0.222222em}{0ex}}1\phantom{\rule{0.222222em}{0ex}}2\phantom{\rule{0.222222em}{0ex}}2\phantom{\rule{0.222222em}{0ex}}3$ (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: 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},
pages = {729--746},
publisher = {EDP-Sciences},
volume = {42},
number = {4},
year = {2008},
doi = {10.1051/ita:2007060},
zbl = {1155.68071},
mrnumber = {2458704},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007060/}
}
TY  - JOUR
AU  - Séébold, Patrice
TI  - Look and Say Fibonacci
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 729
EP  - 746
VL  - 42
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007060/
UR  - https://zbmath.org/?q=an%3A1155.68071
UR  - https://www.ams.org/mathscinet-getitem?mr=2458704
UR  - https://doi.org/10.1051/ita:2007060
DO  - 10.1051/ita:2007060
LA  - en
ID  - ITA_2008__42_4_729_0
ER  - 
%0 Journal Article
%A Séébold, Patrice
%T Look and Say Fibonacci
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 729-746
%V 42
%N 4
%I EDP-Sciences
%U https://doi.org/10.1051/ita:2007060
%R 10.1051/ita:2007060
%G en
%F 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/articles/10.1051/ita:2007060/

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

[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 | Zbl

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

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

[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 | Zbl

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

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

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

[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

[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 | Zbl

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

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

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

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

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

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

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

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

Cited by Sources: