RAIRO - Theoretical Informatics and Applications

Table of Contents - January 2010 - Volume 44, Issue 01 (Special issue dedicated to the 12th "Journées Montoises d'Informatique Théorique")  

Research Article

Infinite words containing squares at every position

Currie, Jamesa1 and Rampersad, Narada1

a1 Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada; j.currie@uwinnipeg.ca, n.rampersad@uwinnipeg.ca

Abstract

Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3.

(Online publication February 11 2010)

Key Words:

  • Infinite words;
  • power-free words;
  • squares.

Mathematics Subject Classification:

  • 68R15.