Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101 (Q2216428)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 7286328
Language Label Description Also known as
default for all languages
No label defined
    English
    Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101
    scientific article; zbMATH DE number 7286328

      Statements

      Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101 (English)
      0 references
      0 references
      0 references
      16 December 2020
      0 references
      A familiar theme in combinatorics on words is the study of words avoiding particular patterns. Although every binary word of length at least 4 contains a square (that is, two consecutive occurrences of the same word), \textit{A. S. Fraenkel} and \textit{R. J. Simpson} [Electron. J. Comb. 2, Research paper R2, 9 p. (1995; Zbl 0816.11007)] found a way to construct arbitrarily long binary words satisfying the FS condition: where the only squares are \(00\), \(11\), and \(0101\). In this paper the authors consider the same question, but for circular words. Their main result is that there is a circular word of length \(m\) satisfying the FS condition if \(m > 73\), and they also characterize all the exceptions.
      0 references
      pattern avoidance
      0 references
      binary circular word
      0 references
      combinatorics on words
      0 references
      squares
      0 references

      Identifiers