# Bounds on this Strategy for Separating Words

Question

Given binary string $$z \in \{0,1\}^n$$, let $$f(z)$$ be the smallest integer $$k$$ such that there exists a DFA with $$k$$ states, such that reading $$z$$ from a specific starting state, we end at a state $$t$$ where either reading a $$0$$ or a $$1$$ at $$t$$ takes us to a new state. (i.e. a state which has not been reached in the path we took when reading $$z$$)

Then, defining $$F(n) = \max\{f(z):z \in \{0,1\}^n\}$$, I was wondering if any bounds are known for $$F$$. Clearly, we have $$F(n) \le n+1$$.

Motivation

Generally, the word separator problem about given distinct binary strings, $$x,y \in \{0,1\}^n, x \neq y$$, to find the smallest DFA such that accepts $$x$$ but not $$y$$.

I was wondering if there have been results on this particular method:

Since $$x\neq y$$, let $$z$$ be the longest common prefix of $$x$$ and $$y$$. (example: if $$x = 1101101,y=1100110$$, then $$z = 110$$ because $$x,y$$ differ on their fourth letter)

WLOG, lets assume $$x= z|0|x', y=z|1|y'$$, where $$|$$ denotes concatenation and $$x',y'$$ are arbitrary. If there exists a DFA of length $$k$$ such reading $$z|0$$ or $$z|1$$ ends at a state $$s'$$ not visited by reading $$z$$, then there is a DFA of length $$k +O(\log(n))$$ separating $$x$$ and $$y$$. (because $$x,y$$ will reach $$s'$$ at different times, it reduces to unary word separation, which is know to take $$O(\log(n))$$ states by prime number theorem)

Rough Ideas

Currently this strategy has stuck out to me: we have that $$f(z) \le g(z_m)+F(n-m)$$ where $$z_m$$ is the subword consisting of the first $$m$$ letters in $$z$$, and $$g(w)$$ is the smallest integer $$k$$ such that there is DFA on $$k$$ states, such that reading $$w$$ at a specific starting state, we end at a new state $$t$$. For upper bounding $$g(w)$$, for any integers $$k,i$$, and any $$w' \in \{0,1\}^k$$, there exists an DFA on $$2k$$ states such that when reading a word $$w$$, we reach the state $$t$$ iff $$w'$$ appears as a factor/substring whose first letter is the $$qk+i$$-th letter of $$w$$. (i.e. the first letter is the $$m$$-th letter of $$w$$ where $$m$$ has the same residue as $$i$$ modulo $$k$$)

Of course, if $$z$$ is a string of only 1's, then $$g(z_m) = m$$ for all $$m$$, thus we need to combine this with a second idea to handle the cases when $$z$$ is periodic or otherwise not quasi-random in some sense, to get a sublinear bound.

• What do you mean precisely by "takes us to a new state"? Do you mean that this new state $s$ is different from $t$, or that the path $i \xrightarrow{z} t$ does not visit $s$? Jul 30 '20 at 7:10
• What do you mean by "$x, y$ will reach $s'$ at different times"? Jul 30 '20 at 7:12
• by new state I meant that the path $i \to t$ did not visit $s$. by $x,y$ will reach $s'$ at different times, I mean that we need to read more letters of $x,y$ before we can possibly reach $s'$. thus, we can append a unary DFA that can only be reached through $s'$ and cannot be exited, which differentiates $x,y$ since they have different number of letters left once they finally reach $s'$. Jul 30 '20 at 20:05
• I don't understand the second clarification. If both $z0$ and $z1$ lead to $s'$, doesn't that mean that both $x$ and $y$ drive the DFA to $s'$ after exactly $|z|+1$ steps? Jul 30 '20 at 20:21
• The first statement is true, the second could be false. For example, if $z = 1111$, then $g(z) = 5$ yet $f(z) = 2$. However, I am hoping to prove that when the values of $g(z_m)$ grow at sufficiently fast rate, that $z$ must have some type of structure which we can use to otherwise bound $f(z)$. Oct 17 '20 at 0:03

The second section of Robson's "Separating strings with small automata" proves $$F(n) = O((n \log n)^{1/2})$$. The string sequence $$(10^n)^n$$ gives a lower bound of $$\Omega(n^{1/2})$$. If the automaton has $$ states then both of the sequences $$\delta_0^{\circ m} (\delta_{(10^n)^{n-1}1}(q_0))$$ and $$\delta_{10^n}^{\circ m}(q_0)$$ will reach a cycle before $$m=n$$.

• I'm sorry, I'm not familiar with this $\delta$ notation. Could someone give a little explanation for what it is? The example seems correct but I'd love to understand the last sentence. Nov 15 '20 at 18:31
• @ZacharyHunter $\delta_s$ is the transition function for reading the letter $s$, and we naturally extend it to $\delta_w$ where $w$ is a word. By the $\circ m$ upper index I just meant the composition of such a function with itself $m$ times. Nov 15 '20 at 18:41
• thanks, makes sense. Nov 15 '20 at 18:48

I believe you have $$F(n) = n+2$$ for all $$n$$.

To prove that $$F(n) \geq n+2$$, we prove $$f(0^n) \geq n+2$$: consider any DFA with at most $$n+1$$ states, and let $$q_0,\ldots, q_{n+1}$$ be the sequence of states visited when reading $$0^{n+1}$$. By the pigeonhole principle, there exist $$0\leq i such that $$q_i = q_j$$, thus $$q_i \cdots q_j$$ is a loop and all the states after $$q_j$$ (in particular q_{n+1}) are part of that loop, hence $$q_{n+1}$$ is not new.

We have $$f(z) \leq n+2$$ for all $$z \in \{0,1\}^n$$ as one can build the automaton consisting of a line of $$n+2$$ states with a loop on the last one (which I think you already noted, with a slight index mistake).

Therefore $$F(n) = n+2$$ for all $$n$$

• The condition is that reading $z|0$ or reading $z|1$ will lead to a new state, not that both of them do. Thus, $f(0^n)=2$: it suffices to take the 2-state automaton that has a $0$-loop on the starting state, and a $1$-transition to the other state. Oct 14 '20 at 14:32
• Yes, Emil is exactly correct. Sorry if my question was not more clear! Oct 16 '20 at 12:51