# 19.4 Separating words problem

Given two words $$u, v$$ of length $$n$$ over $$\{a, b\}$$. Does there always exist an automaton of size $$O(\log n)$$ which distinguishes $$u$$ and $$v$$. Or bigger, like $$O(n^{1/3})$$? Best known bound is about $$O(n^{2/5} \log(n))$$.