Minimum Number of Holes in Unavoidable Sets

Overview

This applet finds the shortest avoiding word for a standard m-uniform set X over an alphabet {a1,...,ak} for m>2, when such a word exists. We define the base set to be the set containing all partial words of length m of the form aim-2aj, with i≤j. A standard m-uniform set X is created by strengthening the base set, i.e. by defining one or more interior positions of some of its words. Only letters from the lower-case English alphabet are accepted. The applet accepts either the caret ^ to denote single holes or integers to denote a string of holes. Rather than entering the entire set X, the user may enter only those words which have been strengthened. The rest of the set will be constructed from these words. The applet may take several minutes or longer for large values of m and k. These guidelines appear in a condensed form below.

Oops! It seems like you don't have the latest JRE. You can get it here .

Instructions for input words

  1. Use only the lowercase letters [a-z], digits [0-9], and the hole character [^].
  2. Words must all be the same length, and entered on separate lines.
  3. Each word must have starting letter lexicographically less than or equal to ending letter, and may not begin or end with holes.
  4. Each set of starting/ending letters may appear at most once.

Examples of valid input words

aaa^b
c4b2c