Bounds on this Strategy for Separating Words

Question

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.

Answer 1

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 $<n$ 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$.

Answer 2

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<j \leq n+1$ 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$