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
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