Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-27T09:01:51.373Z Has data issue: false hasContentIssue false
  • English
  • Français

Look and Say Fibonacci

Published online by Cambridge University Press:  04 January 2008

Patrice Séébold
Patrice Séébold*
Affiliation:
LIRMM, Univ. Montpellier 2, CNRS - 161 rue Ada, 34392 Montpellier, France; [email protected] Département Mathématiques et Informatique Appliquées - UFR4, Université Paul Valéry, Route de Mende, 34199 Montpellier, France.
Get access

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.

Keywords

Look and Say sequenceConwaybinary wordsFibonacci wordmorphismsLyndon factorization.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 4: Fibonacci words , October 2008 , pp. 729 - 746
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations. Cambridge University Press (2003).
Arshon, S., Démonstration de l'existence de suites asymétriques infinies. Mat. Sb. 44 (1937) 769–777 (in Russian), 777–779 (French summary).
J. Berstel, Mots sans carré et morphismes itérés. Discrete Math. 29 (1980). 235–244.
J. Berstel, Fibonacci words – a survey, in The Book of L , edited by G. Rozenberg, A. Salomaa. Springer-Verlag (1986) 13–27.
Berstel, J. and Séébold, P., A characterization of Sturmian morphisms, MFCS'93, Gdansk (Poland). Lect. Notes Comput. Sci. 711 (1993) 281–290. CrossRef
Berstel, J. and Séébold, P., A remark on morphic Sturmian words. RAIRO-Theor. Inf. Appl. 28 (1994) 255–263. CrossRef
Brlek, S., Dulucq, S., Ladouceur, A. and Vuillon, L., Combinatorial properties of smooth infinite words. Theor. Comput. Sci. 352 (2006) 306–317. CrossRef
Cobham, A., Uniform tag sequences. Math. Syst. Theory 6 (1972) 164–192. CrossRef
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.
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).
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).
B. Germain-Bonne, Mots autodescriptifs et co-descriptifs. Laboratoire d'Analyse Numérique et d'Optimisation. Université Lille 1, Research Report ANO 332 (1994).
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).
M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90. Cambridge University Press (2002).
Melançon, G., Lyndon factorization of sturmian words. Discrete Math. 210 (2000) 137–149. CrossRef
Pansiot, J.-J., Hiérarchie et fermeture de certaines classes de tag-systèmes. Acta Informatica 20 (1983) 179–196. CrossRef
Richomme, G., On morphisms preserving infinite Lyndon words. Discrete Math. Theor. Comput. Sci. 9 (2007) 89–108.
Handbook of Formal Languages, Vol. 1, edited by G. Rozenberg, A. Salomaa. Springer (1997).
Séébold, P., On the conjugation of standard morphisms. Theor. Comput. Sci. 195 (1998) 91–109. CrossRef
Séébold, P., About some overlap-free morphisms on a n-letter alphabet. J. Autom. Lang. Comb. 7 (2002) 579–597.
Siromoney, R., Mathew, L., Dare, V.R. and Subramanian, K.G., Infinite Lyndon words. Inform. Process Lett. 50 (1994) 101–104. CrossRef