Squares and overlaps in the Thue-Morse sequence and some variants
Digital Thinkery, 199 Carter Avenue, Waterloo, Ontario N2J 3K5,
2 School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org
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.
Mathematics Subject Classification: 68Q45 / 68R15
Key words: Thue-Morse word / overlap-free word / automatic sequence.
© EDP Sciences, 2006