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))$.
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))$.