Separating words and trace reconstruction

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

Authors

• Zachary Chase 0001

Keywords

• separating words
• trace reconstruction