On discerning strings with finite automata

We study the problem of discerning strings with deterministic finite state automata (DFAs, for short). We begin with a survey on the historical and algorithmic roots of this problem. Then, we focus on the maximun number of states that are necessary to separate two strings of a given length. We survey the most important results concerning this issue and we study the problem from the point of view of some alternative models of automata. The preliminary results concerning the last issue motivate us to formulate a conjecture stating that DFAs can separate any pair of strings by using a logarithmic number of states. We give some evidence supporting our conjecture.