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

Shandy Brown; Narad Rampersad; Jeffrey Shallit; Troy Vasiga

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 3, page 473-484
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Brown, Shandy, et al. "Squares and overlaps in the Thue-Morse sequence and some variants." RAIRO - Theoretical Informatics and Applications 40.3 (2006): 473-484. <http://eudml.org/doc/249704>.

@article{Brown2006,
abstract = { 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. },
author = {Brown, Shandy, Rampersad, Narad, Shallit, Jeffrey, Vasiga, Troy},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Thue-Morse word; overlap-free word; automatic sequence.; automatic sequence},
language = {eng},
month = {10},
number = {3},
pages = {473-484},
publisher = {EDP Sciences},
title = {Squares and overlaps in the Thue-Morse sequence and some variants},
url = {http://eudml.org/doc/249704},
volume = {40},
year = {2006},
}

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
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 3
SP - 473
EP - 484
AB - 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.
LA - eng
KW - Thue-Morse word; overlap-free word; automatic sequence.; automatic sequence
UR - http://eudml.org/doc/249704
ER -

References

top
  1. J.-P. Allouche, J. Currie, and J. Shallit, Extremal infinite overlap-free binary words. Electronic J. Combinatorics5 (1998), #R27 (electronic).  Zbl0890.68107URIhttp://www.combinatorics.org/Volume_5/Abstracts/v5i1r27.html
  2. J.-P. Allouche and J.O. Shallit, The ring of k-regular sequences. Theoret. Comput. Sci.98 (1992) 163–197.  Zbl0774.68072
  3. J.-P. Allouche and J.O. Shallit, The ring of k-regular sequences, II. Theoret. Comput. Sci.307 (2003) 3–29.  Zbl1058.68066
  4. J.-P. Allouche and J.O. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003).  Zbl1086.11015
  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.  Zbl0683.20045
  7. J.J. Pansiot, The Morse sequence and iterated morphisms. Inform. Process. Lett.12 (1981) 68–70.  Zbl0464.68075
  8. H. Prodinger and F.J. Urbanek, Infinite 0–1-sequences without long adjacent identical blocks. Discrete Math.28 (1979) 277–289.  Zbl0421.05007
  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.  Zbl44.0462.01

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.