◊ Minimal Cardinality of Unavoidable Sets ◊

The applet below provides an implementation of our algorithm in Java. This page may not function correctly if you do not have Java Runtime Environment v6u6 and the latest Java Plugin.

The following program takes as input the parameters for a set of partial words. The user may input the length of words in the set, the number of holes per word in the set, and the alphabet over which these words occur. Notice we require the first and last character of a word to be defined (i.e. not a hole). The program will then determine bounds on the minimum cardinality of an unavoidable set of partial words with the given parameters. If possible to calculate efficiently, the program gives exact values for the minimum cardinality.