Remarks on separating words
Erik D. Demaine, Sarah Eisenstat, Jeffrey O. Shallit, Wilson, David A. · arXiv (Cornell University) · 2011
The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length <= n (by accepting one and rejecting the other). In this paper we survey what is known and unknown about the problem, consider some variations, and prove several new results.