Unavoidable Sets of Partial Words

F. Blanchet-Sadri, N. C. Brownstein, and Justin Palumbo


Clearly any set of partial words containing the empty word or a pword consisting only of holes is unavoidable. We shall say that such sets are trivially unavoidable.

If a set of partial words is unavoidable, it must have a factor compatible with each infinite unary word. In particular no nontrivial unavoidable set can have fewer elements than the alphabet. Thus nontrivial unavoidable sets of size 2 exist only if our alphabet is unary or binary. There is nothing interesting to be said about the unavoidable sets over the unary alphabet. The binary alphabet is far more subtle.

We give a java applet which can be used to classify a set of partial words X of size two as avoidable or unavoidable over a binary alphabet. As mentioned before an unavoidable set over the binary alphabet must contain a pword compatible with a factor of both the infinite power of a and the infinite power of b. Thus for the problem it is sufficient to determine the values m1,...,mk and n1,...,nl for which the set {am1a...amka, bn1b...bnlb} is unavoidable. Thus we give two options: the user may select whether he or she wishes to input the pwords directly, or instead to just input the values m1,...,mk and n1,...,nl. The hole symbol is represented by a ^. The applet will attempt to determine if the given set is avoidable or not. If the set is avoidable it will give a word whose infinite power avoids the set. The program may run awhile if the shortest period of an infinite word avoiding the set is sufficiently large; this however seems statistically unlikely.

The applets below provide an implementation of our results in Java. This page may not function correctly if you do not have Java Runtime Environment v1.4.2 and the latest Java Plugin.

Click a button to toggle access to the applet with your preferred input style.