Look and Say Fibonacci
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 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(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 : 10.1051/ita:2007060
Classification : 68R15
Mots clés : 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},
     mrnumber = {2458704},
     zbl = {1155.68071},
     language = {en},
     url = {http://archive.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://archive.numdam.org/articles/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 http://archive.numdam.org/articles/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, Tome 42 (2008) no. 4, pp. 729-746. doi : 10.1051/ita:2007060. http://archive.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

Cité par Sources :