Separating words and trace reconstruction

We prove that for any distinct x,y ∈ 0,1n, there is a deterministic finite automaton with O(n1/3) states that accepts x but not y. This improves Robson’s 1989 bound of O(n2/5). Using a similar complex analytic technique, we improve the upper bound on worst case trace reconstruction, showing that any unknown string x ∈ 0,1n can be reconstructed with high probability from exp(O(n1/5)) independently generated traces.