Avoidable Patterns in Strings of Symbols
by
George McNulty
University of South Carolina

We understand a word to be a string of letters chosen from some alphabet. Mostly, we consider finite words, although words extending infinitely to the right (arranged like the natural numbers) or even extending infinitely to both the left and the right (arranged like the integers) have a role to play in these lectures.

A word u is a subword of a word w provided w=xuy where x and y are words (possibly empty); that is, u is an interval in the string w. We say that the word u is an image or substitution instance of the word v provided there is some map h which associates to each letter in the alphabet for v a word in the alphabet for u so that h(v)=u.

We say that w encounters v when some image of v is a subword of w. Think of v as a kind of pattern and think of each of its images as instances of the pattern. When w encounters v then some instance of the pattern v can be found inside w. We say that w avoids v if and only if w does not encounter v.

Let n be a natural number. The word v is said to be n-avoidable provided on the n-letter alphabet there are infinitely many finite words that avoid v. We say that v is avoidable if it is n-avoidable for some natural number n. A word that is not avoidable is said to be unavoidable. It is not obvious that there are any avoidable words.

This series of lectures is designed to expose the combinatorial theory of avoidable words. This theory has connections to a surprisingly diverse array of mathematical areas. The finite words over a fixed alphabet constitute a free semigroup. The infinite words comprise an interesting topological space and a means to bring the combinatorial theory of words in touch with dynamical systems. Proof theory, a branch of mathematical logic, is concerned in essential ways with manipulations of strings of symbols. In particular, equational proof theory relies on manipulating subterms and substitution instances. Computer programs are strings of symbols and computers themselves can be regarded as devices for manipulating such strings. Given all these conections it is perhaps surprising that the earliest uses of avoidability seem to have arisen to address problems in number theory.

In algebra, the theory of avoidable words had key roles to play in the resolution of Burnside's Conjecture by Novikov and Adjan, in the characterization of inherently nonfinitely based finite semigroups by Mark Sapir, and in Ralph McKenzie's description of finitely generated varieties with polynomially many models.

These three lectures presume no background in the combinatorial theory of words (which is a young field). Each lecture will lead up to an open problem.

Date received: September 18, 2003