We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are -regular. We also prove that changing any finite but nonzero number of bits in the Thue-Morse sequence creates an overlap, and any linear subsequence of the Thue-Morse sequence (except those corresponding to decimation by a power of ) contains an overlap.
Mots clés : Thue-Morse word, overlap-free word, automatic sequence
@article{ITA_2006__40_3_473_0, author = {Brown, Shandy and Rampersad, Narad and Shallit, Jeffrey and Vasiga, Troy}, title = {Squares and overlaps in the {Thue-Morse} sequence and some variants}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {473--484}, publisher = {EDP-Sciences}, volume = {40}, number = {3}, year = {2006}, doi = {10.1051/ita:2006030}, mrnumber = {2269205}, zbl = {1110.68117}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006030/} }
TY - JOUR AU - Brown, Shandy AU - Rampersad, Narad AU - Shallit, Jeffrey AU - Vasiga, Troy TI - Squares and overlaps in the Thue-Morse sequence and some variants JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 473 EP - 484 VL - 40 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006030/ DO - 10.1051/ita:2006030 LA - en ID - ITA_2006__40_3_473_0 ER -
%0 Journal Article %A Brown, Shandy %A Rampersad, Narad %A Shallit, Jeffrey %A Vasiga, Troy %T Squares and overlaps in the Thue-Morse sequence and some variants %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 473-484 %V 40 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006030/ %R 10.1051/ita:2006030 %G en %F ITA_2006__40_3_473_0
Brown, Shandy; Rampersad, Narad; Shallit, Jeffrey; Vasiga, Troy. Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 473-484. doi : 10.1051/ita:2006030. http://www.numdam.org/articles/10.1051/ita:2006030/
[1] Extremal infinite overlap-free binary words. Electronic J. Combinatorics 5 (1998), #R27 (electronic). http://www.combinatorics.org/Volume_5/Abstracts/v5i1r27.html | MR | Zbl
, , and ,[2] The ring of -regular sequences. Theoret. Comput. Sci. 98 (1992) 163-197. | Zbl
and ,[3] The ring of -regular sequences, II. Theoret. Comput. Sci. 307 (2003) 3-29. | Zbl
and ,[4] Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). | MR | Zbl
and ,[5] Axel Thue's Papers on Repetitions in Words: a Translation. Number 20 in Publications du Laboratoire de Combinatoire et d'Informatique Mathématique. Université du Québec à Montréal (February 1995).
,[6] Enumeration of factors in the Thue-Morse word. Disc. Appl. Math. 24 (1989) 83-96. | Zbl
,[7] The Morse sequence and iterated morphisms. Inform. Process. Lett. 12 (1981) 68-70. | Zbl
,[8] Infinite 0-1-sequences without long adjacent identical blocks. Discrete Math. 28 (1979) 277-289. | Zbl
and ,[9] Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1-67. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo (1977) 413-478. | JFM
,Cité par Sources :