It is an open problem how large such an automaton must be, in the worst case, as a function of the length of the input strings.
[1] For proving bounds on this problem, it may be assumed without loss of generality that the inputs are strings over a two-letter alphabet.
[2] Later, Robson (1989) proved the upper bound O(n2/5(log n)3/5) on the automaton size that may be required.
Jeffrey Shallit has offered a prize of 100 British pounds for any improvement to Robson's upper bound.
[6] Several special cases of the separating words problem are known to be solvable using few states: