Look and Say Fibonacci

Séébold, Patrice

doi:10.1051/ita:2007060

Séébold, Patrice

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 4, pp. 729-746.

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.

EuDML MR Zbl

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/

Bibliographie
Cité par

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