Avoidability of palindrome patterns (Q2223455)

This paper deals with the avoidability of palidrome patterns in infinite words. A pattern is a non-empty finite word over an alphabet of capital letters called variables. A pattern is said to be \(k\)-avoidable if there exists an infinite word over a \(k\)-letter alphabet that avoids it. The avoidability index of a pattern is the size of the smallest such alphabet. A formula is obtained from a pattern by replacing every isolated variable (with only one appearance) by a dot. The factors between the dots are called fragments. A palindrome pattern is equal to its mirror image. The authors ``characterize the formulas that are avoided by every \(\alpha\)-free word for some \(\alpha > 1\) and show that the avoidable formulas whose fragments are of the form \(XY\) or \(XYX\) are 4-avoidable. The largest avoidability index of an avoidable palindrome pattern is known to be at least 4 and at most 16.'' They ``make progress toward the conjecture that every avoidable palindrome pattern is 4-avoidable.''