On some interesting ternary formulas (Q5894536)

A ternary formula \(f\) consists of several \textit{fragments} over the alphabet \(\Delta=\{A,B,C\}\) separated by dots: \(f=f_1.f_2 \dots f_k\). Its \textit{occurrence} in a word \(w\) over another alphabet \(\Sigma\) is a non-erasing morphism \(h: \Delta^* \to \Sigma^*\) such that for every fragment \(f_i\) of \(f\), \(h(f_i)\) appears as a factor of \(w\). If \(w\) does not admit occurrences of \(f\), it is said to \textit{avoid it}, and the general question of the theory is: What is the minimal alphabet over which a given formula can be avoided on an infinite number of words, or, which is the same, on infinite words? If it is avoided, how many words of length \(n\) avoid it? The paper contains several examples of ternary formulas with interesting avoidance properties, including some formulas avoided by basically only one ternary infinite word, another avoided by polynomially many binary words of a given length, and a formula which looks like a palindrome and is avoidable over the 4-letter but not over the 3-letter alphabet. It also contains a more general result: All \textit{nice} ternary formulas, meaning that for every variable \(X\) of \(f\) there exists a fragment of \(f\) that contains \(X\) at least twice, are avoidable over the 3-letter alphabet. The results of the paper were obtained by a technique using both a computer-based case study and theoretic arguments.