Separating words problem

Unsolved problem in computer science:
How many states are needed in a <a href="/facts/Deterministic_finite_automaton/9conRLFS">deterministic finite automaton</a> that behaves differently on two given <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a> of length n?
<a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">(more unsolved problems in computer science)</a>

<p>In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, the separating words problem is the problem of finding the smallest <a href="/facts/Deterministic_finite_automaton/9conRLFS">deterministic finite automaton</a> that behaves differently on two given <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a>, meaning that it accepts one of the two strings and rejects the other string. It is an <a href="/facts/Open_problem/VuR6yLsW">open problem</a> how large such an automaton must be, in the worst case, as a function of the length of the input strings.
</p>

Separating words problem open-in-new

Separating words problem