<p>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).</p>

<p>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.)</p>

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

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

<p>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}$.</p>

<p>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?</p>

CC BY-SA 3.0
2011-07-30T19:34:13.443Z
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:http://portal.acm.org/citation.cfm?id=1577108
Aryeh
CC BY-SA 3.0
2011-07-30T19:38:04.300Z
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.
Aryeh
CC BY-SA 3.0
2011-07-30T20:20:41.287Z
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.
domotorp
CC BY-SA 3.0
2015-07-26T01:28:16.477Z
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.
amnn
CC BY-SA 3.0
2015-07-26T13:15:57.450Z
@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?
domotorp
CC BY-SA 3.0
2015-07-27T22:28:22.810Z
@domotorp, The third paragraph introduces the reduction, but I don't think it justifies it any way (it merely states an equivalence that is not proven).
amnn
CC BY-SA 3.0
2015-07-28T08:27:40.310Z
@amnn: Are you suggesting that there is something wrong with the first part of Kaveh's comment (upvoted many times) where he claims that $K_n(x,y)=m/2+(M-m)/4$?
domotorp
CC BY-SA 3.0
2015-07-28T22:12:53.300Z
Well consider a DFA M with states q1, q2, q3, q4. q1 is the start state, q2, q3 are final states, and q4 is a sink state. There is a transition from q1 to q2 on 0 and from q1 to q3 on 1. All other transitions go to q4. Now M recognizes the language `{0, 1}` but it does not follow that running M on 0 and running M on 1 result in reaching the same state.
amnn
CC BY-SA 3.0
2015-07-29T08:10:59.627Z
@amnn: I think that you should finally read Kaveh's comment that I'm referring to and then we can continue our discussion.
domotorp
CC BY-SA 3.0
2015-07-29T16:27:33.193Z
If you mean the comment that starts "Here is an idea", then I have read it. It *also* states the reduction without justification.
amnn
CC BY-SA 3.0
2015-07-29T19:28:24.080Z
@amnn: I think it's proof is pretty straightforward. If $x$ and $y$ go to the same state, then there is 50% chance of them being both accepted, while if they go to different states, there is 25% chance. As you can see from the comments, many people agreed with this, so maybe you have misunderstood something (or all of us were wrong - one can never be sure...).
domotorp
CC BY-SA 3.0
2015-07-29T20:28:27.713Z
What you say is correct, but for a reduction to be valid, it must work *in both ways*. I.e. x and y are both accepted by a machine M if and only if x and y reach the same state. Your argument satisfies the `<=` direction, but not the `=>` which I refuted with my earlier counter-example. Both directions are needed here because otherwise you could be under-counting (x and y reaching the same state is only one way they could both be accepted by the same machine).
amnn
CC BY-SA 3.0
2015-07-30T07:03:31.453Z
@amnn: But we have expressed $K_n(x,y)$ with $m$ and $M$, so in my answer I only deal with computing $m$, i.e., when they go to the same state.
domotorp
CC BY-SA 3.0
2011-07-30T17:50:54.067Z
2011-07-31T09:21:54.743Z
2011-07-31T09:21:54.743Z
domotorp
<p>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:</p>

<p>On input $x$, $y$ where $x,y\in\Sigma^*$</p>

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

<p>b. increment $c$ if both simulation runs are accepting</p></li>
<li>output $c$</li>
</ol>

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

CC BY-SA 3.0
2011-07-30T16:02:56.010Z
Clearly trying all machines will work.  Aryeh wants to know if there's, perhaps, a polynomial time algorithm or otherwise some hardness result.
Lev Reyzin
CC BY-SA 3.0
2011-07-30T16:25:51.817Z
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.
domotorp
CC BY-SA 3.0
2011-07-30T16:59:00.243Z
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.
Lev Reyzin
CC BY-SA 3.0
2011-07-30T19:40:01.990Z
Right, thanks for pointing out the loophole, Kai. It's been fixed :)
Aryeh
CC BY-SA 3.0
2011-07-30T07:57:20.740Z
2011-07-30T07:57:20.740Z
Kai
<p>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 <em>all</em> DFAs (not just connected, minimal, or non-degenerate ones); thus, $|DFA(n)| = n^{2n}2^n$.</p>

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

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

<p>This question has implications for <a href="http://portal.acm.org/citation.cfm?id=1577108">machine learning</a>.</p>

<p>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 <em>both</em> $x$ and $y$. Question: can $K_n(x,y)$ be computed in time $poly(n,|x|,|y|)$?</p>

CC BY-SA 3.0
2011-07-26T18:02:33.797Z
Are the counted automata supposed to accept *only* $x$ and $y$?
Raphael
CC BY-SA 3.0
2011-07-26T18:20:07.140Z
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?".
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2011-07-26T20:12:54.403Z
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$.
Srivatsan Narayanan
CC BY-SA 3.0
2011-07-26T20:33:27.520Z
A good place to find such answers: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Shallit:Jeffrey.html
Vijay D
CC BY-SA 3.0
2011-07-26T21:01:20.897Z
@Raphael, no. I'm pretty sure Aryeh wants both $x$ and $y$ accepted, and he doesn't care about what happens to the other strings.
Lev Reyzin
CC BY-SA 3.0
2011-07-27T11:08:18.373Z
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?
Aryeh
CC BY-SA 3.0
2011-07-27T14:00:30.313Z
@Aryeh: No one can start a bounty on this question yet.  The question has to be at least 48 hours old.  More here: http://cstheory.stackexchange.com/privileges/set-bounties
Aaron Sterling
CC BY-SA 3.0
2011-07-27T15:38:24.303Z
A very naive answer is that this problem is in  #P , since computing if a given $DFA$ accepts both $x$ and $y$ is in P (actually it is in $O(n)$). From looking a bit at this problem, I would suggest that the difficulty arises mostly from checking how $x$ and $y$ interact, i.e. how can you alter the DFA while keeping the invariant of accepting both strings.
chazisop
CC BY-SA 3.0
2011-07-28T20:12:29.683Z
What size does the smallest automaton $A^*$ that accepts $x$ and $y$ (amongst others) have? If you got that, is it a minor of all the automata you want to count? If so, there probably is a closed expression in terms of $A^*$.
Raphael
CC BY-SA 3.0
2011-07-29T13:08:00.783Z
The smallest automaton that accepts $x$ and $y$ has a single state, so I don't think it's terribly informative...
Aryeh
CC BY-SA 3.0
2011-07-30T11:04:12.627Z
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$.
Kaveh
CC BY-SA 3.0
2011-07-30T14:13:05.310Z
@Kaveh: I absolutely agree with the first part of your comment but I do not get the second part.
domotorp
CC BY-SA 3.0
2011-07-30T14:46:08.257Z
@domotorp: it is not a complete solution for computing $m$, but Which one is not clear? 1. removing the shared initial part, 2. wlog $x=0^a$ and $y=1^b$. (more)
Kaveh
CC BY-SA 3.0
2011-07-30T14:50:27.567Z
I think the unclear part is the last part. If we know the number of binary DAGs with height at most $\max\{a,b\}$ and $s$ states and $l$ leaves (missed it above) then we will know the number of $n$ state DFAs that extend them, and then we can sum over the values of $s$ and $l$ to get $m$.
Kaveh
CC BY-SA 3.0
2011-07-30T16:55:27.843Z
@Kaveh let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/949/discussion-between-domotorp-and-kaveh)
domotorp
CC BY-SA 3.0
2011-07-30T19:31:34.617Z
Kaveh is right about $K_n(x,y)=\frac12m+\frac14(M-m)$ -- which means that $\frac14|DFA(n)|\le K_n(x,y)\le\frac12|DFA(n)|$. I don't quite follow the second part, after discarding the initial segment.
Aryeh
<cc.complexity-theory><fl.formal-languages><automata-theory><counting-complexity>
How many DFAs accept two given strings?
Aryeh
# How many DFAs accept two given strings?

(Asked by: username_0 on 2011-07-26)

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](http://portal.acm.org/citation.cfm?id=1577108).

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|)$?

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory, counting-complexity
> **Comments:**
> **username_1**: Are the counted automata supposed to accept *only* $x$ and $y$?  
> **username_2**: 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?".  
> **username_3**: 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$.  
> **username_4**: A good place to find such answers: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Shallit:Jeffrey.html  
> **username_5**: @Raphael, no. I'm pretty sure Aryeh wants both $x$ and $y$ accepted, and he doesn't care about what happens to the other strings.  
> **username_0**: 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?  
> **username_6**: @Aryeh: No one can start a bounty on this question yet.  The question has to be at least 48 hours old.  More here: http://cstheory.stackexchange.com/privileges/set-bounties  
> **username_7**: A very naive answer is that this problem is in  #P , since computing if a given $DFA$ accepts both $x$ and $y$ is in P (actually it is in $O(n)$). From looking a bit at this problem, I would suggest that the difficulty arises mostly from checking how $x$ and $y$ interact, i.e. how can you alter the DFA while keeping the invariant of accepting both strings.  
> **username_1**: What size does the smallest automaton $A^*$ that accepts $x$ and $y$ (amongst others) have? If you got that, is it a minor of all the automata you want to count? If so, there probably is a closed expression in terms of $A^*$.  
> **username_0**: The smallest automaton that accepts $x$ and $y$ has a single state, so I don't think it's terribly informative...  
> **username_8**: 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$.  
> **username_9**: @Kaveh: I absolutely agree with the first part of your comment but I do not get the second part.  
> **username_8**: @domotorp: it is not a complete solution for computing $m$, but Which one is not clear? 1. removing the shared initial part, 2. wlog $x=0^a$ and $y=1^b$. (more)  
> **username_8**: I think the unclear part is the last part. If we know the number of binary DAGs with height at most $\max\{a,b\}$ and $s$ states and $l$ leaves (missed it above) then we will know the number of $n$ state DFAs that extend them, and then we can sum over the values of $s$ and $l$ to get $m$.  
> **username_9**: @Kaveh let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/949/discussion-between-domotorp-and-kaveh)  
> **username_0**: Kaveh is right about $K_n(x,y)=\frac12m+\frac14(M-m)$ -- which means that $\frac14|DFA(n)|\le K_n(x,y)\le\frac12|DFA(n)|$. I don't quite follow the second part, after discarding the initial segment.  

---

## 2 answers

### Answer by username_9 on 2011-07-30. Score: 1

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?

> **Comments:**
> **username_0**: 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:http://portal.acm.org/citation.cfm?id=1577108  
> **username_0**: 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.  
> **username_9**: 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.  
> **username_10**: 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.  
> **username_9**: @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?  
> **username_10**: @domotorp, The third paragraph introduces the reduction, but I don't think it justifies it any way (it merely states an equivalence that is not proven).  
> **username_9**: @amnn: Are you suggesting that there is something wrong with the first part of Kaveh's comment (upvoted many times) where he claims that $K_n(x,y)=m/2+(M-m)/4$?  
> **username_10**: Well consider a DFA M with states q1, q2, q3, q4. q1 is the start state, q2, q3 are final states, and q4 is a sink state. There is a transition from q1 to q2 on 0 and from q1 to q3 on 1. All other transitions go to q4. Now M recognizes the language `{0, 1}` but it does not follow that running M on 0 and running M on 1 result in reaching the same state.  
> **username_9**: @amnn: I think that you should finally read Kaveh's comment that I'm referring to and then we can continue our discussion.  
> **username_10**: If you mean the comment that starts "Here is an idea", then I have read it. It *also* states the reduction without justification.  
> **username_9**: @amnn: I think it's proof is pretty straightforward. If $x$ and $y$ go to the same state, then there is 50% chance of them being both accepted, while if they go to different states, there is 25% chance. As you can see from the comments, many people agreed with this, so maybe you have misunderstood something (or all of us were wrong - one can never be sure...).  
> **username_10**: What you say is correct, but for a reduction to be valid, it must work *in both ways*. I.e. x and y are both accepted by a machine M if and only if x and y reach the same state. Your argument satisfies the `<=` direction, but not the `=>` which I refuted with my earlier counter-example. Both directions are needed here because otherwise you could be under-counting (x and y reaching the same state is only one way they could both be accepted by the same machine).  
> **username_9**: @amnn: But we have expressed $K_n(x,y)$ with $m$ and $M$, so in my answer I only deal with computing $m$, i.e., when they go to the same state.  

---

### Answer by username_11 on 2011-07-30. Score: 0

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

> **Comments:**
> **username_5**: Clearly trying all machines will work.  Aryeh wants to know if there's, perhaps, a polynomial time algorithm or otherwise some hardness result.  
> **username_9**: 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.  
> **username_5**: 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.  
> **username_0**: Right, thanks for pointing out the loophole, Kai. It's been fixed :)  

---

