9
$\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$
7
  • $\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 '20 at 7:10
  • $\begingroup$ What do you mean by "$x, y$ will reach $s'$ at different times"? $\endgroup$
    – J.-E. Pin
    Jul 30 '20 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$ Jul 30 '20 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$ Jul 30 '20 at 20:21
  • 1
    $\begingroup$ 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)$. $\endgroup$ Oct 17 '20 at 0:03
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 15 '20 at 18:31
  • 2
    $\begingroup$ @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. $\endgroup$
    – acupoftea
    Nov 15 '20 at 18:41
  • $\begingroup$ thanks, makes sense. $\endgroup$ Nov 15 '20 at 18:48
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$

$\endgroup$
2
  • 3
    $\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$ Oct 14 '20 at 14:32
  • $\begingroup$ Yes, Emil is exactly correct. Sorry if my question was not more clear! $\endgroup$ Oct 16 '20 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.