5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – J.-E. Pin Jul 30 at 7:10
  • $\begingroup$ What do you mean by "$x, y$ will reach $s'$ at different times"? $\endgroup$ – J.-E. Pin Jul 30 at 7:12
  • $\begingroup$ 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'$. $\endgroup$ – Zachary Hunter Jul 30 at 20:05
  • $\begingroup$ 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? $\endgroup$ – Radu GRIGore Jul 30 at 20:21
  • $\begingroup$ I find it useful to think that I'm constructing the DFA on the go, only determine 0 edges and 1 edges when I need to. if $z|0$ takes us to $s'$, which has never been reached before, then there exists we can have $z|1$ not lead to $s'$. (if the 1 edge at that state has already been used previously, then obviously it does not lead to $s'$, as it has never been reached, otherwise, the 1 edge is also undetermined, so we may choose to have it not lead to $s'$) alternatively we could say that the DFA may be modified such that $x$ and $y$ are driven to $s'$ after a different number of steps. $\endgroup$ – Zachary Hunter Jul 30 at 20:29
0
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Oct 14 at 14:32
  • $\begingroup$ Yes, Emil is exactly correct. Sorry if my question was not more clear! $\endgroup$ – Zachary Hunter Oct 16 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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