• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Cyclically Repetition-Free Words on Small Alphabets

Tero Harju, Dirk Nowotka, Cyclically Repetition-Free Words on Small Alphabets . Information Processing Letters 110, 591–595, 2010.

Abstract:

All sufficiently long binary words contain a square
but there are infinite binary words having only the short
squares 00, 11 and 0101. Recently it was shown by J. Currie
that there exist cyclically square-free words in a ternary
alphabet except for lengths 5, 7, 9, 10, 14, and 17.
We consider binary words all conjugates of which contain
only short squares. We show that the number c(n) of these
binary words of length n grows unboundedly. I
n order for this, we show that there are morphisms
that preserve circular square-free words in the ternary alphabet.

BibTeX entry:

@ARTICLE{jHaNo10a,
  title = {Cyclically Repetition-Free Words on Small Alphabets },
  author = {Harju, Tero and Nowotka, Dirk},
  journal = {Information Processing Letters},
  volume = {110},
  pages = {591–595},
  year = {2010},
  keywords = {repetition-free words, cyclic words, square-free words},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication