New results on pseudosquare avoidance (Q2333047)

The paper deals with binary words with minimum possible occurrences of squares (\(xx\)) and antisquares (\(x\overline{x}\), where \(\overline{x}\) is obtained from \(x\) by changing 1 in 0, and 0 in 1). The problem of determining the length of the longest binary word having at most \(a\) distinct squares and at most \(b\) distinct antisquares is completely solved. Among others, the following important theorems are proved: \begin{itemize} \item There exists an infinite word over the binary alphabet \(\{0, 1\}\) that avoids \(xx\) and \(x\overline{x}\) for all \(x\) with \(|x|\ge 3\). \item No infinite word over a finite alphabet avoids all factors of the form \(xh(x)\), for all nonerasing morphisms \(h\), with \(|x|\ge 4.\) \item There exists an infinite binary word that avoids all factors of the form \(xh(x)\) and \(h(x)x\), for all nonerasing binary morphisms \(h\), with \(|x| \ge 5\). \end{itemize} In the future, the authors plan to consider similar questions for abelian avoidability problems. For the entire collection see [Zbl 1419.68014].