A Sharper Upper Bound for the Separating Words Problem

Abstract

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/3}{\log }^{7}n)$

An error has been identified in the proof of Theorem 1. Correcting the argument presented yields an upper bound which does not improve upon existing results (e.g., [Chase 2020]), so this paper does not in fact provide an improved upper bound. We therefore withdraw our claim of a stronger result