Words avoiding repetitions in arithmetic progressions

Jui Yi Kao, Narad Rampersad, Jeffrey O. Shallit, Manuel Almeida Silva

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

Carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. We show a connection between Carpi's construction and the paperfolding words. We extend Carpi's result by constructing uncountably many words that avoid squares in arithmetic progressions of odd difference. We also construct infinite words avoiding overlaps and infinite words avoiding all sufficiently large squares in arithmetic progressions of odd difference. We use these words to construct labelings of the 2-dimensional integer lattice such that any line through the lattice encounters a squarefree (resp. overlapfree) sequence of labels.
Original languageEnglish
Pages (from-to)126-137
Number of pages12
JournalTheoretical Computer Science
Volume391
Issue number1-2
DOIs
Publication statusPublished - 4 Feb 2008

Keywords

  • Paperfolding word
  • Repetition
  • Arithmetic progression

Fingerprint

Dive into the research topics of 'Words avoiding repetitions in arithmetic progressions'. Together they form a unique fingerprint.

Cite this