Squares and overlaps in the Thue-Morse sequence and some variants

Brown, Shandy; Rampersad, Narad; Shallit, Jeffrey; Vasiga, Troy

doi:10.1051/ita:2006030

Brown, Shandy ; Rampersad, Narad ; Shallit, Jeffrey ; Vasiga, Troy

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 473-484.

Résumé

We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are $2$ -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 $2$ ) contains an overlap.

MR Zbl | 1 citation dans Numdam

DOI : 10.1051/ita:2006030

Classification : 68Q45, 68R15
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 = {https://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  - https://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 https://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. https://www.numdam.org/articles/10.1051/ita:2006030/

Bibliographie
Cité par

[1] J.-P. Allouche, J. Currie, and J. Shallit, Extremal infinite overlap-free binary words. Electronic J. Combinatorics 5 (1998), #R27 (electronic). http://www.combinatorics.org/Volume_5/Abstracts/v5i1r27.html | MR | Zbl

[2] J.-P. Allouche and J.O. Shallit, The ring of $k$ -regular sequences. Theoret. Comput. Sci. 98 (1992) 163-197. | Zbl

[3] J.-P. Allouche and J.O. Shallit, The ring of $k$ -regular sequences, II. Theoret. Comput. Sci. 307 (2003) 3-29. | Zbl

[4] J.-P. Allouche and J.O. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). | MR | Zbl

[5] J. Berstel, 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] S. Brlek, Enumeration of factors in the Thue-Morse word. Disc. Appl. Math. 24 (1989) 83-96. | Zbl

[7] J.J. Pansiot, The Morse sequence and iterated morphisms. Inform. Process. Lett. 12 (1981) 68-70. | Zbl

[8] H. Prodinger and F.J. Urbanek, Infinite 0-1-sequences without long adjacent identical blocks. Discrete Math. 28 (1979) 277-289. | Zbl

[9] A. Thue, Ü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

Schaeffer, Luke; Shallit, Jeffrey The first-order theory of binary overlap-free words is decidable, Canadian Journal of Mathematics, Volume 76 (2024) no. 4, p. 1144 | DOI:10.4153/s0008414x23000342
SPIEGELHOFER, LUKAS GAPS IN THE THUE–MORSE WORD, Journal of the Australian Mathematical Society, Volume 114 (2023) no. 1, p. 110 | DOI:10.1017/s1446788721000380
Du, Chen Fei; Shallit, Jeffrey; Shur, Arseny M. Optimal Bounds for the Similarity Density of the Thue-Morse Word with Overlap-Free and 73-Power-Free Infinite Binary Words, International Journal of Foundations of Computer Science, Volume 26 (2015) no. 08, p. 1147 | DOI:10.1142/s012905411540016x
Du, Chen Fei; Shallit, Jeffrey Similarity density of the Thue-Morse word with overlap-free infinite binary words, Electronic Proceedings in Theoretical Computer Science, Volume 151 (2014), p. 231 | DOI:10.4204/eptcs.151.16
Shallit, Jeffrey Decidability and Enumeration for Automatic Sequences: A Survey, Computer Science – Theory and Applications, Volume 7913 (2013), p. 49 | DOI:10.1007/978-3-642-38536-0_5
CHARLIER, ÉMILIE; RAMPERSAD, NARAD; SHALLIT, JEFFREY ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES, International Journal of Foundations of Computer Science, Volume 23 (2012) no. 05, p. 1035 | DOI:10.1142/s0129054112400448
Charlier, Émilie; Rampersad, Narad; Shallit, Jeffrey Enumeration and Decidable Properties of Automatic Sequences, Developments in Language Theory, Volume 6795 (2011), p. 165 | DOI:10.1007/978-3-642-22321-1_15
Currie, James; Rampersad, Narad Infinite words containing squares at every position, RAIRO - Theoretical Informatics and Applications, Volume 44 (2010) no. 1, p. 113 | DOI:10.1051/ita/2010007
Moshe, Yossi On the subword complexity of Thue–Morse polynomial extractions, Theoretical Computer Science, Volume 389 (2007) no. 1-2, p. 318 | DOI:10.1016/j.tcs.2007.10.015

Cité par 9 documents. Sources : Crossref