# Error in Robson's proof about separating strings?

One of my students discovered a possible mistake in Robson's classic paper Separating strings with small automata.
The issue is in the proof of Theorem 1, giving the simpler bound $$O(\sqrt{n\log n})$$.
The proof goes by giving an automaton that finds a substring of length $$O(\sqrt{n\log n})$$ in $$u$$ that ends in $$i$$ such that $$u_i\ne v_i$$ is the first place where the words $$u$$ and $$v$$ differ.
It is correctly proved that the given substring cannot occur in $$v$$ up to $$i$$, starting with some required modulo, but the issue is that the substring can arise after $$i$$.
I think that he is right, and see no way of saving the proof.

ps. Note that the best claimed bound in Robson is $$\tilde O(n^{2/5})$$ recently a better bound, $$\tilde O(n^{1/3})$$ was proved by Chase.

• Isn't that taken care of in the paragraph just before Theorem 1? If the accepting state is reached at some $v_j$, then we necessarily have $j>i$, and we can compose the automata with one that separates $v_{j+1}\ldots v_n$ and $u_{i+1}\ldots u_n$, which have different lengths so are easy to separate. Commented Nov 24, 2023 at 17:30
• @Tassle You are 100% right, I've failed to notice that part. Do you want to convert your comment to an answer so that I can accept it? Commented Nov 24, 2023 at 20:01

This is taken care of in the paragraph just before Theorem 1. If the accepting state is reached at some $$v_j$$, then we necessarily have $$j>i$$, and we can compose the automaton with one that separates $$v_{j+1}\ldots v_n$$ and $$u_{i+1}\ldots u_n$$, which have different lengths so are easy to separate.
• I also have another question in light of this. Is it possible that any two strings can be separated in this manner in $O(\log n)$? Equivalently, given two strings of length $n$ that differ only in their last bit, can we always separate them with an $O(\log n)$ state automaton that has a unique accept state which is a sink, so once you enter it you stay there for good? Commented Nov 25, 2023 at 7:02