A Sharper Upper Bound for the Separating Words Problem

We show that for any two distinct words $s_1,s_2$ over an arbitrary alphabets, there exists a deterministic finite automaton with $O({\log }^{2}n)$ states that accepts $s_1$ and rejects $s_2$. This improves the previous upper bound of $O(n^{1\mathrm{/}3}{\log }^{7}n)$