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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101
scientific article

    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