28
$\begingroup$

Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected, minimal, or non-degenerate ones); thus, $|DFA(n)| = n^{2n}2^n$.

Now consider two strings $x,y\in\Sigma^*$ and define $K(x,y)$ to be the number of elements of $DFA(n)$ that accept both $x$ and $y$.

Question: What is the complexity of computing $K(x,y)$?

This question has implications for machine learning.

Edit: Now that there's a bounty on this question, I suppose a bit more precision in the formulation is in order. For $n\ge1$, let $DFA(n)$ be the collection of $n^{2n}2^n$ automata, as defined above. For $x,y\in\{0,1\}^*$, define $K_n(x,y)$ to be the number of automata in $DFA(n)$ that accept both $x$ and $y$. Question: can $K_n(x,y)$ be computed in time $poly(n,|x|,|y|)$?

$\endgroup$
  • 2
    $\begingroup$ If you fix a DFA without fixing the final states, then either it maps x and y to the same state, in which case the only constraint is that the state has to be final, or it maps them to two different states, in which case the only constraint is that they both have to be final. Thus, I would reword your problem as "how many DFAs map x and y to different states?". $\endgroup$ – a3nm Jul 26 '11 at 18:20
  • 3
    $\begingroup$ Aryeh, can you explain the count $n^{2n} 2^n$? I cannot get the $2^n$ factor. Added: Oops, I forgot to specify the final states. Anyway, for the sake of others, here's how the count goes. For each state, specify where to go on inputs $0$ and $1$; that accounts for $n^{2n}$. Specify the set of final states; that's $2^n$. $\endgroup$ – Srivatsan Narayanan Jul 26 '11 at 20:12
  • 2
    $\begingroup$ Indeed, I don't care what happens to strings other than $x$ and $y$. I guess one needs a certain amount of points to start a bounty? $\endgroup$ – Aryeh Jul 27 '11 at 11:08
  • 4
    $\begingroup$ The smallest automaton that accepts $x$ and $y$ has a single state, so I don't think it's terribly informative... $\endgroup$ – Aryeh Jul 29 '11 at 13:08
  • 3
    $\begingroup$ Here is an idea: we only need to know the number of $n$-state DFAs which end up in the same state on $x$ and $y$. Let this number be $m$ and $M$ be the total number of DFAs, i.e. $M=n^{2n}2^{n}$ . Then the answer is $\frac{1}{2}m + \frac{1}{4}(M-m)$, this gives bounds. To compute $m$ another idea is that we can forget about the shared initial segment of $x$ and $y$ and also assume that w.l.o.g. $x=0^a$ and $b=1^b$. We only to count the number of binary DAGs with $l$ states and height at most $\max\{a,b\}$ that $0^a$ and $1^b$ end up in the same place and from that it is easy to compute $m$. $\endgroup$ – Kaveh Jul 30 '11 at 11:04
1
$\begingroup$

So the question is pretty brief but very interesting. I suppose that the input is $n$ in unary, and $x$ and $y$ in binary (or we have problems, as pointed out by Kai's answer).

First of all, if you are interested in knowing $K(x,y)$ approximately, then you can just generate a few random DFA's and this will give you (whp) a good approximation. (I wonder if this complexity class has a name.)

Then knowing $K(x,y)$ precisely seems like a tough problem. As pointed out in the comments by a3_nm and Kaveh, the question is equivalent to determining the number of automata for which $x$ and $y$ go to the same state. I will denote the probability that they go to the same state by $p$.

Update: Some of the things I wrote here were not true, now I fixed them.

It is easy to see that $p \ge 1/n$. We have equality, if $x$ is all 0's and $y$ is all zero except for its last bit, which is a 1. Are there other cases? I don't know. If for example $x$ is the empty string and $y=00$, then $p= \frac{n+1}{(n-1)n}$.

To simplify the problem, I even started to think about what happens if $x$ and $y$ are unary. If both are at least $n$ and their difference is divisible by $n!$, then $p=1$. Is there a simple formula for the unary version?

$\endgroup$
  • $\begingroup$ I've clarified the problem -- a $poly(n,|x|,|y|)$ algorithm is desired (or a reduction from some known hard problem). The sampling approximation is employed in the paper where this kernel is introduced:portal.acm.org/citation.cfm?id=1577108 $\endgroup$ – Aryeh Jul 30 '11 at 19:34
  • 2
    $\begingroup$ As for the unary version: there are only polynomially many $n$-state unary automata, so I would bet that there is a poly-time algorithm for computing $K_n(x,y)$ for this case. $\endgroup$ – Aryeh Jul 30 '11 at 19:38
  • $\begingroup$ Indeed, you are absolutely right that the unary version is computable. I still wonder how simple the formula is for a given x and y. $\endgroup$ – domotorp Jul 30 '11 at 20:20
  • $\begingroup$ The reduction you have used is buggy: x and y may be accepted by the same automata and end in completely different states, in fact, they may share only the starting state in their paths, which is true for all strings. $\endgroup$ – amnn Jul 26 '15 at 1:28
  • $\begingroup$ @amnn: It has been three years since I wrote this, but doesn't the third para of my answer explain why I deal only with ending in the same state? $\endgroup$ – domotorp Jul 26 '15 at 13:15
0
$\begingroup$

I may very well be missing the point but you stated that $n$ is fixed, so all DFAs of that size could be considered precomputed and stored in an easily simulatable format. Compute $K$ as follows:

On input $x$, $y$ where $x,y\in\Sigma^*$

  1. store $x$ and $y$
  2. initialize counter $c$ to $0$
  3. for each of your $n^{2n} 2^n$ DFAs
  4. a. simulate it on both words (this step is $\mathcal{O}(|xy|)$)

    b. increment $c$ if both simulation runs are accepting

  5. output $c$

Altogether, the computation has linear complexity. The answer is quite different for $K(n,x,y)$.

$\endgroup$
  • 3
    $\begingroup$ Clearly trying all machines will work. Aryeh wants to know if there's, perhaps, a polynomial time algorithm or otherwise some hardness result. $\endgroup$ – Lev Reyzin Jul 30 '11 at 16:02
  • $\begingroup$ Strictly speaking this is polynomial time in the input, if n is not part of the input, that is what Kai was saying. But the question is clearly different. $\endgroup$ – domotorp Jul 30 '11 at 16:25
  • 4
    $\begingroup$ Oh I see. I don't think that's what he means by "fix $n$." I think the natural interpretation of the problem is one that doesn't trivialize it. $\endgroup$ – Lev Reyzin Jul 30 '11 at 16:59
  • 1
    $\begingroup$ Right, thanks for pointing out the loophole, Kai. It's been fixed :) $\endgroup$ – Aryeh Jul 30 '11 at 19:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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