Title:  The Separating Words Problem

Given two different strings (words) x and w, we consider the simplest posssible computational problem: to tell them apart. How hard can it be?

In other words, using a simple computing model, such as the finite automaton, how many states are needed to accept w and reject x, or vice versa? Surprisingly, the answer is not known, and the known upper and lower bounds are quite far apart. I will survey this problem and consider some interesting variations.

The slides of Dr. Shallit's talk can be found here.