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.
This implementation makes heavy use of our results. First it checks if the inputted
set is of one of the forms identified in our paper. If it is, the appropriate response
is immediately outputted. Otherwise it searches for an avoiding word using a modified
brute force procedure which only checks for reasonable candidates. In our paper
we conjecture that we have identified every possible unavoidable set of size 2.
If this is true any unavoidable set will always be caught in the initial stages
of the procedure. Thus the algorithm will always halt if and only if our conjecture
is true.
The following are the unavoidability results we have proven.
For any nonnegative integer p, the set {am1a...amka, bn1b...bnlb} is unavoidable if and only if
the set
{ap(m1+1)-1a...ap(mk+1)-1a, bp(n1+1)-1b...bp(nl+1)-1b} is unavoidable.
If k, l=1 then {am1a,bn1b} is unavoidable if and only if the greatest powers of
2 dividing m+1 and n+1 are different.
If k=1, l=2 then {am1a,bn1bn2b} is unavoidable
under the following conditions.
The set {am1a,bn1b} is unavoidable, m1=2n1+n2+2 or m=n2-n1-2, and n1+1
divides n2+1.
m1=n2-n1-1 or 2n1+n2+2, and the highest power of 2 dividing n1+1 is less than the
highest power of 2 dividing m1+1.
n1 is less than n2, 2m1=n1+n2 and m-n1 divides m1+1.
m1=6, n1=1, n2=3.
Our conjecture is that these results and their symmetric equivalents give a complete
classification of the unavoidable sets for k=1, l less than or equal to 2.
We have also shown that if the conjecture is true the set {am1a...amka, bn1b...bnl
b} is avoidable for all k,l greater than or equal to 2.
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.
Input the values m1,...,mk on the left and n1,...,nl on the right. Separate each
value by a space.
m1a...a
