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

DOI10.1016/J.TCS.2020.10.029MaRDI QIDQ2216428zbMATH OpenOpenAlexFDO

Authors James D. Currie, Jesse T. Johnson

Publication date 16 December 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.09742

zbMATH Keywords

binary circular wordcombinatorics on wordspattern avoidancesquares

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We characterize exactly the lengths of binary circular words containing no squares other than 00, 11, and 0101. Key words: combinatorics on words, circular words, necklaces, square-free words, non-repetitive sequences

Review text

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.

Recommendations

• Cyclically repetition-free words on small alphabets
• scientific article; zbMATH DE number 1948509
• How many square occurrences must a binary sequence contain?
• scientific article; zbMATH DE number 1943964
• New results on pseudosquare avoidance

Cites work

• Avoiding large squares in infinite binary words
• Circularly squarefree words and unbordered conjugates: a new approach
• Cyclically repetition-free words on small alphabets
• How many squares must a binary sequence contain?
• scientific article; zbMATH DE number 5605093 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1948509 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• On ternary square-free circular words
• Repetition avoidance in circular factors

Cited in

(4)

• Attainable lengths for circular binary words avoiding \(k\) powers
• scientific article; zbMATH DE number 1943964 (Why is no real title available?)
• The length of the longest sequence of consecutive FS-double squares in a word
• Cyclically repetition-free words on small alphabets

This page was built for publication: Characterization of the lengths of binary circular words containing no squares other than 00, 11, and 0101

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216428)