A new upper bound for separating words

Abstract

We prove that for any distinct $x,y\in \{0,1{\}}^n$, there is a deterministic finite automaton with $\tilde{O}(n^{1/3})$ states that accepts $x$ but not $y$. This improves Robson's 1989 upper bound of $\tilde{O}(n^{2/5})$.

14 pages

Cited by in corpus (2)

• New upper bounds for trace reconstruction
• A Data-Structure for Approximate Longest Common Subsequence of A Set of Strings