Unavoidable Sets
Abstract   Implementation   Paper (PDF)  


Francine Blanchet-Sadri, Sean Simmons and Eric Weissenstein

The applet below provides an implementation of the Zimin algorithm in Java. This page may not function correctly if you do not have Java 1.6 or higher from Sun Microsystems.

The user inputs any string of ASCII characters into the input box, and the program treats it as a word over the alphabet of ASCII characters. We limit you to only use up to 6 distinct characters. It then generates the Zimin graph, and proceeds to use the algorithm to test whether the word is irreducible or not, which tells us whether it is avoidable or not. The program then outputs the result to the screen.