Look and Say Fibonacci

Patrice Séébold

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

How to cite

top

Séébold, Patrice. "Look and Say Fibonacci." RAIRO - Theoretical Informatics and Applications 42.4 (2010): 729-746. <http://eudml.org/doc/92900>.

@article{Séébold2010,
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},
keywords = {Look and Say sequence; Conway; binary words; Fibonacci word; morphisms; Lyndon factorization.; look and say sequence; Lyndon factorization},
language = {eng},
month = {3},
number = {4},
pages = {729-746},
publisher = {EDP Sciences},
title = {Look and Say Fibonacci},
url = {http://eudml.org/doc/92900},
volume = {42},
year = {2010},
}

TY - JOUR
AU - Séébold, Patrice
TI - Look and Say Fibonacci
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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.; look and say sequence; Lyndon factorization
UR - http://eudml.org/doc/92900
ER -

References

top
  1. J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations. Cambridge University Press (2003).  
  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).  
  3. J. Berstel, Mots sans carré et morphismes itérés. Discrete Math. 29 (1980). 235–244.  
  4. J. Berstel, Fibonacci words – a survey, in The Book of L, edited by G. Rozenberg, A. Salomaa. Springer-Verlag (1986) 13–27.  
  5. J. Berstel and P. Séébold, A characterization of Sturmian morphisms, MFCS'93, Gdansk (Poland). Lect. Notes Comput. Sci.711 (1993) 281–290.  
  6. J. Berstel and P. Séébold, A remark on morphic Sturmian words. RAIRO-Theor. Inf. Appl.28 (1994) 255–263.  
  7. S. Brlek, S. Dulucq, A. Ladouceur and L. Vuillon, Combinatorial properties of smooth infinite words. Theor. Comput. Sci.352 (2006) 306–317.  
  8. A. Cobham, Uniform tag sequences. Math. Syst. Theory6 (1972) 164–192.  
  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.  
  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).  
  14. M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press (2002).  
  15. G. Melançon, Lyndon factorization of sturmian words. Discrete Math.210 (2000) 137–149.  
  16. J.-J. Pansiot, Hiérarchie et fermeture de certaines classes de tag-systèmes. Acta Informatica20 (1983) 179–196.  
  17. G. Richomme, On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci.9 (2007) 89–108.  
  18. Handbook of Formal Languages, Vol. 1, edited by G. Rozenberg, A. Salomaa. Springer (1997).  
  19. P. Séébold, On the conjugation of standard morphisms. Theor. Comput. Sci.195 (1998) 91–109.  
  20. P. Séébold, About some overlap-free morphisms on a n-letter alphabet. J. Autom. Lang. Comb.7 (2002) 579–597.  
  21. R. Siromoney, L. Mathew, V.R. Dare and K.G. Subramanian, Infinite Lyndon words. Inform. Process Lett.50 (1994) 101–104.  

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.