Let $A$ be an alphabet of $k$ symbols, and $p$ a pattern. An example of a pattern is $p=XX$, where $X$ is any finite string of symbols from $A^+$. Avoiding $p$ is avoiding any subword repeated twice in a row. Such strings are called square-free.

It is well known that there are no infinite binary ($k=2$) strings of symbols that are square-free (in fact, only $0$, $1$, $01$, $10$, $010$, and $101$ are square-free), but there are infinite ternary ($k=3$) square-free strings, as proved by Axel Thue.

Other examples: the patterns $X$ and $XYX$ are unavoidable on any alphabet.

My question is:

Q. Is there a theorem of the form: Any alphabet $A$ with $|A| \le k$ cannot avoid any patterns $p$ of the form [some description of these patterns $p$ as a function of $k$], i.e., there are no infinite strings that avoid these $p$?

In other words, is there a pattern to—a characterization of—the patterns that are unavoidable, for a given $k$? Or are there, to date, only claims that specific patterns are unavoidable?


According to the 2013 paper "Computing the Partial Word Avoidability Indices of Ternary Patterns" by Blanchet-Sadri, Lohr, and Scott,

The problem of deciding whether a given pattern is avoidable has been solved [1, 14], but the one of deciding whether it is k-avoidable has remained open.

So, it seems to be an open problem.

  • $\begingroup$ Thanks, Bjørn! [14] is Zimin's 1984 paper. Apparently Zimin characterized unavoidable patterns. But as you indicate, without restriction to $k$ symbols. $\endgroup$ – Joseph O'Rourke Jul 19 '14 at 1:31
  • 1
    $\begingroup$ @JosephO'Rourke An interesting factoid that you didn't mention is that the famous Thue-Morse word 01101001... avoids the pattern XYXYX, and such words are called "overlap-free" (or "irreducible" or "strongly cube-free") because any overlap of a word with itself would have to follow such a pattern. $\endgroup$ – Bjørn Kjos-Hanssen Jul 19 '14 at 1:43
  • 2
    $\begingroup$ The English language does not consist of irreducible words only, however, as there is "alfalfa". $\endgroup$ – Bjørn Kjos-Hanssen Jul 19 '14 at 1:44
  • $\begingroup$ Great example! Maybe entente qualifies as an overlap word, but it is really French (cf. détente). Surely overlap words exist in many languages... $\endgroup$ – Joseph O'Rourke Jul 19 '14 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.