Unavoidable Sets

Francine Blanchet-Sadri, Brandon Blakeley and Josh Gunter

Implementation

Given an alphabet and a set of partial words, our program will determine whether the set is avoidable or not as well as other properties of the set. To specify the set X, input partial words using the '^' character for holes. Each partial word should be separated by a new line.

To input words with a large number of holes, we recommend using the Powers input mode. In this mode, the word "a^^^^^^a" (an 'a', followed by 6 holes, and then ending with an 'a') can be input as "a6a." However, in this input mode, the characters 0-9 are forbidden from the alphabet.

Short circuiting means that when using results, only the first result the program finds will be output. If the short circuit button is not checked, then all known results regarding the set X will be output. For quicker results, we recommend not searching for the shortest avoiding word.

Notice: on most input, the program will output the result in a matter of seconds; however on some input the program takes between several minutes to several hours. The program may be stopped at any time with the "Halt" button (which will appear once a computation has begun).

The implementation of our results requires Java 1.4.2 or higher from Sun Microsystems. A stand-alone version in Python may be released at a later date.