6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Nov 24, 2023 at 17:30
  • $\begingroup$ @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? $\endgroup$
    – domotorp
    Nov 24, 2023 at 20:01

1 Answer 1

8
+200
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Thanks Tassle. I was about to give the same answer. J.M. Robson. $\endgroup$ Nov 24, 2023 at 21:20
  • $\begingroup$ 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? $\endgroup$
    – domotorp
    Nov 25, 2023 at 7:02
  • $\begingroup$ @domotorp, does this answer your question: cstheory.stackexchange.com/questions/47292/… $\endgroup$ Nov 25, 2023 at 8:46
  • $\begingroup$ @Zach Indeed it does! $\endgroup$
    – domotorp
    Nov 25, 2023 at 9:44
  • $\begingroup$ @john What is the best email to contact you at? $\endgroup$ Nov 25, 2023 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.