Separating Words by Automata

Gödel’s Lost Letter and P=NP 2019-09-09

Another exponential gap in complexity theory?

[ From his home page ]

Jeffrey Shallit is a famous researcher into many things, including number theory and being a skeptic. He has a colorful website with an extensive quotation page—one of my favorites by Howard Aiken is right at the top:

Don’t worry about people stealing an idea. If it’s original, you will have to ram it down their throats.

Today I thought I would discuss a wonderful problem that Jeffrey has worked on.

Jeffrey’s paper is joint with Erik Demaine, Sarah Eisenstat, and David Wilson. See also his talk. They say in their introduction:

Imagine a computing device with very limited powers. What is the simplest computational problem you could ask it to solve? It is not the addition of two numbers, nor sorting, nor string matching—it is telling two inputs apart: distinguishing them in some way.

More formally:

Let ${x}$ and ${y}$ be two distinct ${n}$ long strings over the usual binary alphabet. What is the size of the smallest deterministic automaton ${M}$ that can accept one of the strings and reject the other?

That is, how hard is it for a simple type of machine to tell ${x}$ apart from ${y}$ ? There is no super cool name for the question—it is called the Separating Words Problem (SWP).

Some History

Pavel Goral&ccaron;ik and Vaclav Koubek introduced the problem in 1986—see their paper here. Suppose that ${x}$ and ${y}$ are distinct binary words of length ${n}$ . Define ${\bf{SEP}(x,y)}$ to be the number of states of the smallest automaton that accepts ${x}$ and rejects ${y}$ or vice-versa. They proved the result that got people interested:

Theorem 1 For all distinct binary words ${x}$ and ${y}$ of length ${n}$ ,
$\displaystyle {\bf SEP}(x,y) =o(n).$

That is the size of the automaton is asymptotically sub-linear. Of course there is trivially a way to tell the words apart with order ${n}$ states. The surprise is that one can do better, always.

In 1989 John Robson obtained the best known result:

Theorem 2 For all distinct binary words ${x}$ and ${y}$ of length ${n}$ ,
$\displaystyle {\bf SEP}(x,y) = O(n^{2/5}(\log n)^{3/5}).$

This bound is pretty strange. We rarely see bounds like it. This suggest to me that it is either special or it is not optimal. Not clear which is the case. By the way it is also known that there are ${x}$ and ${y}$ so that

$\displaystyle {\bf SEP}(x,y) = \Omega(\log n).$

Thus there is an exponential gap between the known lower and upper bounds. Welcome to complexity theory.

What heightens interest in this gap is that whenever the words have different lengths, there is always a logarithmic-size automaton that separates them. The reason is our old friend, the Chinese Remainder Theorem. Simply, if ${m < n}$ there is always a short prime ${p}$ that does not divide ${n - m}$ , which means that the DFA that goes in a cycle of length ${p}$ will end in a different state on any ${x}$ of length ${m}$ from the state on any ${y}$ of length ${n}$ . Moreover, the strings ${0^m}$ and ${0^N}$ where ${N}$ equals ${m}$ plus the least common multiple of ${1,\dots,m+1}$ require ${\Omega(\log N)}$ states to separate. Padding these with ${1}$ s gives equal-length pairs of all lengths ${n}$ giving SEP(x,y) ${\sim \log n}$ .

Some other facts about SWP can be found in the paper:

(a) It does not matter whether the alphabet is binary or larger.
(b) For random distinct ${x,y}$ , the expected number of states needed to separate them is at most ${4}$ .
(c) All length- ${n}$ pairs ${x,y}$ can be distinguished by deterministic pushdown automata (with two-way input tape) of size ${O(\log n)}$ .

Point (b) underscores why it has been hard to find “bad pairs” that defeat all small DFAs. All this promotes belief that logarithmic is the true upper bound as well. Jeffrey stopped short of calling this a conjecture in his talk, but he did offer a 100-pound prize (the talk was in Britain) for improving Robson’s bound.

Some Questions

There are many partial results in cases where ${x}$ and ${y}$ are restricted in some way. See the papers for details. I thought I would just repeat a couple of interesting open cases.

${\bullet }$ How hard is it to tell words from their reversal? That is, if ${x}$ is a word can we prove a better bound on

$\displaystyle {\bf SEP}(x,x^{R}).$

Recall ${x^{R}}$ is the reversal of the word ${w}$ . Of course we assume that ${x}$ is not the same as its reversal—that is, we assume that ${x}$ is not a palindrome.

${\bullet }$ How hard is it to tell words apart from their cyclic shifts?

${\bullet }$ How hard is it to tell words from their ${\dots}$ You get the idea: try other operations on words.

Open Problems

The SWP is a neat question in my opinion. I wonder if there would be some interesting consequence if we could always tell two words apart with few states. The good measure of a conjecture is: how many consequences are there that follow from it? I wonder if there could be some interesting applications. What do you think?