<p>Converting my comment to an answer:</p>
<p>This is taken care of in the paragraph just before Theorem 1. If the accepting state is reached at some <span class="math-container">$v_j$</span>, then we necessarily have <span class="math-container">$j&gt;i$</span>, and we can compose the automaton with one that separates <span class="math-container">$v_{j+1}\ldots v_n$</span> and <span class="math-container">$u_{i+1}\ldots u_n$</span>, which have different lengths so are easy to separate.</p>

CC BY-SA 4.0
2023-11-24T21:20:36.247Z
Thanks Tassle. I was about to give the same answer. J.M. Robson.
John Michael Robson
CC BY-SA 4.0
2023-11-25T07:02:56.593Z
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?
domotorp
CC BY-SA 4.0
2023-11-25T08:46:27.170Z
@domotorp, does this answer your question: https://cstheory.stackexchange.com/questions/47292/bounds-on-this-strategy-for-separating-words
Zach Hunter
CC BY-SA 4.0
2023-11-25T09:44:40.933Z
@Zach Indeed it does!
domotorp
CC BY-SA 4.0
2023-11-25T14:51:37.633Z
@john What is the best email to contact you at?
mathworker21
CC BY-SA 4.0
2023-11-25T16:44:17.350Z
jrobson@u-bordeaux.fr
John Michael Robson
CC BY-SA 4.0
2023-11-27T09:15:44.773Z
Please don't add "thank you" as an answer. Instead, vote up the answers that you find helpful. - [From Review](/review/low-quality-posts/30177)
Jan Johannsen
CC BY-SA 4.0
2023-11-29T08:32:13.747Z
@Jan The answer of Tassle was not there yet, it was only in a comment. Otherwise, I agree.
domotorp
CC BY-SA 4.0
2023-11-25T09:01:37.540Z
2023-11-25T09:01:37.540Z
Tassle
<p>One of my students discovered a possible mistake in Robson's classic paper <a href="https://doi.org/10.1016/0020-0190(89)90215-9" rel="noreferrer">Separating strings with small automata</a>.<br />
The issue is in the proof of Theorem 1, giving the simpler bound <span class="math-container">$O(\sqrt{n\log n})$</span>.<br />
The proof goes by giving an automaton that finds a substring of length <span class="math-container">$O(\sqrt{n\log n})$</span> in <span class="math-container">$u$</span> that ends in <span class="math-container">$i$</span> such that <span class="math-container">$u_i\ne v_i$</span> is the first place where the words <span class="math-container">$u$</span> and <span class="math-container">$v$</span> differ.<br />
It is correctly proved that the given substring cannot occur in <span class="math-container">$v$</span> up to <span class="math-container">$i$</span>, starting with some required modulo, but the issue is that the substring can arise after <span class="math-container">$i$</span>.<br />
I think that he is right, and see no way of saving the proof.</p>
<p>ps. Note that the best claimed bound in Robson is <span class="math-container">$\tilde O(n^{2/5})$</span> recently a better bound, <span class="math-container">$\tilde O(n^{1/3})$</span> was proved by <a href="https://arxiv.org/abs/2007.12097" rel="noreferrer">Chase</a>.</p>

CC BY-SA 4.0
2023-11-24T17:30:28.073Z
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.
Tassle
CC BY-SA 4.0
2023-11-24T20:01:25.290Z
@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?
domotorp
<automata-theory><dfa>
Error in Robson's proof about separating strings?
domotorp
# Error in Robson's proof about separating strings?

(Asked by: username_0 on 2023-11-22)

One of my students discovered a possible mistake in Robson's classic paper [Separating strings with small automata](https://doi.org/10.1016/0020-0190(89)90215-9).  
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](https://arxiv.org/abs/2007.12097).

**Tags:** automata-theory, dfa
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  

---

## 1 answers

### Answer by username_1 on 2023-11-25. Score: 8 | Accepted answer

Converting my comment to an answer:

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.

> **Comments:**
> **username_2**: Thanks Tassle. I was about to give the same answer. J.M. Robson.  
> **username_0**: 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?  
> **username_3**: @domotorp, does this answer your question: https://cstheory.stackexchange.com/questions/47292/bounds-on-this-strategy-for-separating-words  
> **username_0**: @Zach Indeed it does!  
> **username_4**: @john What is the best email to contact you at?  
> **username_2**: jrobson@u-bordeaux.fr  
> **username_5**: Please don't add "thank you" as an answer. Instead, vote up the answers that you find helpful. - [From Review](/review/low-quality-posts/30177)  
> **username_0**: @Jan The answer of Tassle was not there yet, it was only in a comment. Otherwise, I agree.  

---

