18
$\begingroup$

One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$. I am curious if there any results about the ability of a random DFA to separate two given (nonrandom) strings.

Clearly a random DFA with sufficiently many states separates strings with high probability. Specifically, if $u,v \in \Sigma^n$, a random DFA with $O(n)$ states is unlikely to ever revisit the same state once it reaches the first place where $u$ and $v$ differ, and therefore separates $u$ and $v$.

Can we do better? Ideally, what is the smallest $f(n)$ s.t. that a random DFA with $f(n)$ states separates strings of length $n$ with positive probability (or perhaps probability $\ge 1/2$)? A brief search didn't turn up many results on the properties of random DFAs; all I could find was http://arxiv.org/abs/1311.6830.

Improve this question
$\endgroup$
6
  • $\begingroup$ Positive probability isn't a particularly useful condition here, given that it's just a restatement of the open problem. High probability still might be interesting. $\endgroup$
    – Geoffrey Irving
    May 12, 2014 at 16:37
  • 1
    $\begingroup$ What does "separates" mean? Accepts one and rejects the other? If so, is it obvious that $O(n)$ states suffices? $\endgroup$
    – usul
    May 14, 2014 at 3:11
  • $\begingroup$ Yes, separates means accepts exactly one. And you're right: the most trivial separation argument actually requires $O(n^2)$ states (what I wrote above is wrong), though I would be surprised if many fewer didn't suffice. $\endgroup$
    – Geoffrey Irving
    May 14, 2014 at 3:23
  • 1
    $\begingroup$ Wouldn't you expect the bounds to depend on how much the words differ? It seems like words that differ by a single letter would be harder to discriminate at random, because you need to discriminate at that one transition, and very different words would be easier. [To generalize, you can forget about the longest common prefix (you reach a random state from that); then, differing letters send you either to the same state or to different states; then if the states are different you need to look at the proba of resyncing, and staying in sync (starts depending again on the words)...] $\endgroup$
    – a3nm
    May 14, 2014 at 10:22
  • $\begingroup$ Yes, like the open problem, I am interested in the hardest possible words to discriminate. Words that differ in only a few places can already be separated by $O(\log n)$ states, so they are unlikely to be the hard case. $\endgroup$
    – Geoffrey Irving
    May 14, 2014 at 17:05

2 Answers 2

Reset to default
6
$\begingroup$

It appears, via code, that if you take a random string $x$ and then form $y$ by flipping only the first bit of $x$, then a random DFA on $n/5$ states fails to separate $x,y$ with high probability. So, in particular, there exists a pair $x,y$ such that a random DFA on $n/5$ states fails to separate $x,y$ with high probability.

Improve this answer
$\endgroup$
0
1
$\begingroup$

[Edit: this answer does not work, see comments.]

This is just an informal idea and I don't know if it helps, but it's too long to be given as a comment. Also, I am not at all familiar with random DFAs, so maybe I have a wrong intuition of how you should reason about probabilities on them, but hopefully this is not entirely worthless.

I will suppose that your bounds should depend on how much $u$ and $v$ differ; if they don't, it seems clear to me that the worst case are strings differing only by their first character (strings differing at a set $X$ of positions have more chances of being told apart than strings differing at a set $Y \subset X$ of positions, I'd say, and putting the difference as early as possible gives you opportunity to resynchronize).

I will also look at the probability that the words are distinguished, namely, they reach different states. I guess you would then need to adapt for being accepted or rejected based on how your random DFAs allocate final states. If each state has a probability 1/2 of being final, then when the strings end up at the same state they are not distinguished, and when they end up at different states they have probability 1/2 of being distinguished.

Now I will consider the word $w$ obtained from $u$ and $v$ as follows: $w_i = 1$ if $u_i = v_i$, and $w_i = 0$ otherwise. I think it is clear that $w$ is the only interesting thing to consider about $u$ and $v$.

Now, define $p(i)$ the probability that we are at the same state after reading prefixes of length $i$ of $u$ and $v$, and $q(i) = 1 - p(i)$ the probability that we aren't.

I think we have $p(i+1) = p(i) + q(i)/n$ when $w_{i+1}$ is $1$. Intuitively, we are at the same state after reading $i+1$ letters either when we were at the same state after reading $i$, or when we were at two different (random) states, we drew two transitions to random states, and they happened to be the same one. Likewise, we have $p(i+1) = 1/n$ when $w_{i+1}$ is $0$: you are drawing two random states, no matter where you started from.

From this I think you could compute the probability of being at the same state after reading $u$ and $v$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Unfortunately, it is far from obvious that $w$ is the only interesting property of $u$ and $v$. The easiest way to see this is that there is trivially a nonzero probability of distinguishing any nontrivial $w$ from $0^n$; indeed, only two states suffice regardless of $n$. However, as discussed in arxiv.org/pdf/1103.4513.pdf, there are words $u,v$ of length $n$ s.t. no $o(\log n)$ state DFA can distinguish them. This contradicts your formulas for $p(i)$. $\endgroup$
    – Geoffrey Irving
    May 14, 2014 at 17:12
  • 1
    $\begingroup$ To clarify, your formulas would be correct if the DFA transitions were a random function of the string index; since they are independent of index, the probabilities are correlated in a rather complicated fashion. $\endgroup$
    – Geoffrey Irving
    May 14, 2014 at 17:17
  • $\begingroup$ I'm afraid I don't get your counterexample. There is a $>0$ prba, with two states, of distinguishing $0^n$ and $w \neq 0^n$, OK; and maybe there are words of length $n$ that cannot be told apart with $o(\log n)$ states. But how does it contradict my claim that $w$ is the only important thing, or my formulae for $p(i)$? As for correlations, I see there might be a catch of the kind you're mentioning but I don't understand yet why it fails exactly. If you go twice through the same state, there is a correlation, but is there a reason to think it would influence in a certain direction on average? $\endgroup$
    – a3nm
    May 14, 2014 at 21:51
  • $\begingroup$ If $p(n) < 1$, $u$ and $v$ are distinguished with positive probability. However, for sufficiently large $n$ and small numbers of states we know that $p(n) = 1$ for some $u$ and $v$. Since your formulas imply that if $p(i) < 1$ then $p(i+1) = p(i) + (1-p(i))/n = p(i)(1-1/n)+1/n < 1$, your formula is not capturing the fact that certain $u$ and $v$ are impossible to distinguish. $\endgroup$
    – Geoffrey Irving
    May 15, 2014 at 0:19
  • $\begingroup$ Ah... right, I understand. If no small DFA can distinguish two words, then no random DFA can distinguish them either. So indeed there is a problem with my approach, the probability $q(i)$ should drop to zero eventually, because of those correlations, it seems. Sorry for providing an incorrect answer. $\endgroup$
    – a3nm
    May 15, 2014 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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