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

Improve this question
$\endgroup$
16
  • 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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 11:04

2 Answers 2

Reset to default
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?

Improve this answer
$\endgroup$
13
  • $\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, 2011 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, 2011 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, 2011 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, 2015 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, 2015 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)$.

Improve this answer
$\endgroup$
4
  • 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, 2011 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, 2011 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, 2011 at 16:59
  • 1
    $\begingroup$ Right, thanks for pointing out the loophole, Kai. It's been fixed :) $\endgroup$
    – Aryeh
    Jul 30, 2011 at 19:40

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.