Look and Say Fibonacci

Patrice Séébold

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

  • Volume: 42, Issue: 4, page 729-746
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Séébold, Patrice. "Look and Say Fibonacci." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 42.4 (2008): 729-746. <http://eudml.org/doc/246029>.

@article{Séébold2008,
abstract = {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(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 $LS$ operator, focusing in particular on the Fibonacci word.},
author = {Séébold, Patrice},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {look and say sequence; Conway; binary words; Fibonacci word; morphisms; Lyndon factorization},
language = {eng},
number = {4},
pages = {729-746},
publisher = {EDP-Sciences},
title = {Look and Say Fibonacci},
url = {http://eudml.org/doc/246029},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Séébold, Patrice
TI - Look and Say Fibonacci
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2008
PB - EDP-Sciences
VL - 42
IS - 4
SP - 729
EP - 746
AB - 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(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 $LS$ operator, focusing in particular on the Fibonacci word.
LA - eng
KW - look and say sequence; Conway; binary words; Fibonacci word; morphisms; Lyndon factorization
UR - http://eudml.org/doc/246029
ER -

References

top
  1. [1] J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations. Cambridge University Press (2003). Zbl1086.11015MR1997038
  2. [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). Zbl0018.11503JFM63.0928.01
  3. [3] J. Berstel, Mots sans carré et morphismes itérés. Discrete Math. 29 (1980). 235–244. Zbl0444.20050MR560766
  4. [4] J. Berstel, Fibonacci words – a survey, in The Book of L , edited by G. Rozenberg, A. Salomaa. Springer-Verlag (1986) 13–27. Zbl0589.68053
  5. [5] J. Berstel and P. Séébold, A characterization of Sturmian morphisms, MFCS’93, Gdansk (Poland). Lect. Notes Comput. Sci. 711 (1993) 281–290. Zbl0925.11026MR1265070
  6. [6] J. Berstel and P. Séébold, A remark on morphic Sturmian words. RAIRO-Theor. Inf. Appl. 28 (1994) 255–263. Zbl0883.68104MR1282447
  7. [7] S. Brlek, S. Dulucq, A. Ladouceur and L. Vuillon, Combinatorial properties of smooth infinite words. Theor. Comput. Sci. 352 (2006) 306–317. Zbl1116.11014MR2207527
  8. [8] A. Cobham, Uniform tag sequences. Math. Syst. Theory 6 (1972) 164–192. Zbl0253.02029MR457011
  9. [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. MR922073
  10. [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. [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. [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. [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). Zbl0514.20045MR1475463
  14. [14] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press (2002). Zbl1001.68093MR1905123
  15. [15] G. Melançon, Lyndon factorization of sturmian words. Discrete Math. 210 (2000) 137–149. Zbl0946.68113MR1731611
  16. [16] J.-J. Pansiot, Hiérarchie et fermeture de certaines classes de tag-systèmes. Acta Informatica 20 (1983) 179–196. Zbl0507.68046MR727164
  17. [17] G. Richomme, On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci. 9 (2007) 89–108. Zbl1152.68490MR2306522
  18. [18] Handbook of Formal Languages, Vol. 1, edited by G. Rozenberg, A. Salomaa. Springer (1997). Zbl0866.68057MR1469992
  19. [19] P. Séébold, On the conjugation of standard morphisms. Theor. Comput. Sci. 195 (1998) 91–109. Zbl0981.68104MR1603835
  20. [20] P. Séébold, About some overlap-free morphisms on a n -letter alphabet. J. Autom. Lang. Comb. 7 (2002) 579–597. Zbl1095.68090MR1990460
  21. [21] R. Siromoney, L. Mathew, V.R. Dare and K.G. Subramanian, Infinite Lyndon words. Inform. Process Lett. 50 (1994) 101–104. Zbl0803.68093MR1281048

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.