论文标题
分开单词的新上限
A new upper bound for separating words
论文作者
论文摘要
我们证明，对于任何独特的$ x，y \ in \ {0,1 \}^n $，有一个确定性有限自动机，带有$ \ widetilde {o}（n^{1/3}）$状态，该状态接受$ x $，但不是$ y $。这改善了罗布森（Robson）的1989年$ \ widetilde {o}（n^{2/5}）$的上限。
We prove that for any distinct $x,y \in \{0,1\}^n$, there is a deterministic finite automaton with $\widetilde{O}(n^{1/3})$ states that accepts $x$ but not $y$. This improves Robson's 1989 upper bound of $\widetilde{O}(n^{2/5})$.
