A Sharper Upper Bound for the Separating Words Problem

Bogdan C. Dumitru

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…