9
$\begingroup$

I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source where I can find algorithms such cases?

In order to not make the question too broad, the following structure is of particular interest: all the DFAs to intersect operate in the binary alphabet (0|1), they can also use don't care symbols. Moreover, all the states have only one transition except for at most K special states, which have only two transitions (and these transitions are always 0 or 1, but no don't care). K is an integer, less than 10 for practical purposes. Also, they have a single accepting state. Additionally, it is known that the intersection is ALWAYS a DFA in form of "strip", i.e., no branches as in the following image:

enter image description here

EDIT: Perhaps the description of the constraint on the input DFAs is not very clear. I will try to improve it in this paragraph. You have as input T DFAs. Each of these DFAs operates only on the binary alphabet. Each of them has at most N states. For each DFA, each of its states is one of the following:

1) the accepting state (it is only one and there's no transition from it to any other state)

2) a state with two transitions (0 and 1) to the same target state (the majority of the states is of this kind)

3) a state with two transitions (0 and 1) to different target states (at most K of this kind)

It is guaranteed that there's only one accepting state and that there are at most K states of type (3) in each input DFA. It is also guaranteed that the intersection DFA of all the input DFAs is a "strip" (as described above), of size less than N.

EDIT2: Some additional constraints, as requested by D.W. in the comments:

  • The input DFAs are DAGs.
  • The input DFAs are "levelled", following the D.W. definition in the comments. Namely, you can assign different integers to every state in such a way that every transitions goes from an integer u to an integer v, such that u + 1 = v.
  • The number of accepting states for each input DFA, doesn't exceed K.

Any ideas? Thanks.

$\endgroup$
  • $\begingroup$ How exactly do you model "don't care"? It seems to make the automata nondeterministic, in a way. $\endgroup$ – Shaull Jan 5 '15 at 7:26
  • $\begingroup$ @Shaull Why should it make the automaton non deterministic. That can happen only if there is another transition from the same state, which is explicitly excluded. $\endgroup$ – babou Jan 5 '15 at 10:51
  • 1
    $\begingroup$ What is a DFA in form of "strip", i.e., no branches? Do yu have any specific reason to believe one can do better than the standard algorithm in your case? $\endgroup$ – babou Jan 5 '15 at 10:55
  • 1
    $\begingroup$ Hi. Computing the actual intersection would be great, since it would simplify many things, but deciding the emptiness would be useful as well. $\endgroup$ – ale64bit Jan 5 '15 at 17:11
  • 1
    $\begingroup$ just ran across a new paper on intersection graphs, could some of this theory be relevant? could you plz expand on your application mentioned in your comment in Theoretical Computer Science Chat? & invite others to continue further discussion there. $\endgroup$ – vzn Jan 6 '15 at 2:30
9
$\begingroup$

Yes, there are some cases of the DFA non emptiness insersection problem that are inside P. My master's thesis is devoted to this question, but unfortunately it is in French. However, most of the results have appeared here in $[2]$.

When the alphabet is unary, then the problem is L-complete when each DFA has at most two final states, and NP-complete otherwise. Most of the other cases are restriction on the transition monoids of the automata. For example, for abelian group transition monoids, the problem is in $\text{NC}^3$ when each DFA has at most one final state, and NP-complete otherwise; for elementary 2-group transition monoids, the problem is $\oplus$L-complete when each DFA has at most two final states, and NP-complete otherwise.


Let me now address your more precise question, which can only be found in $[1]$. Suppose you are given DFAs working over $\{0,1\}$ and shaped as trees, i.e there exists a state $u$ (initial state) such that for each state $v$ there exists a unique path from $u$ to $v$. Then, deciding the intersection non emptiness is:

  1. L-complete for one final state in each DFA,
  2. NL-complete for two final states in each DFA, and
  3. NP-complete for three or more final states in each DFA.

The hardness results still hold even if you "fork" respectively 0, 1 or 2 times (this is your $K$). Now if your DFAs are directed acyclic graphs instead of trees, then the problem is NP-complete even with one final state in each DFA and $K=2$; the reduction is quite straightforward and is from Monotone 1-in-3 3-SAT.

Therefore, no, I don't think there is an efficient algorithm for your problem.

Now, if the number of automata is fixed, you might want to discuss with Michael Wehar who has recently published $[3]$.


EDIT: Since OP edited his question, let me clarify my answer with his new requirements. Consider the NP-complete problem Monotone 1-in-3 3-SAT where you are given a formula in 3-CNF without negation, and where you have to determine whether there is an assignment that makes exactly one variable true in each clause. You can reduce this problem to the non emptiness intersection problem as follows. For example, for the clause $x_2 \lor x_3 \lor x_5$, you build the following automaton:

$\hskip2in$reduction gadget

Note that the automata are trees (and hence DAGs), are levelled, and have three final states. Actually, the three final states coud be merged into a single one, if one is satisfied with DAGs. Moreover, only two states have two (distinct) outgoing transitions.

  1. Michael Blondin. Complexité raffinée du problème d'intersection d'automates, M.Sc. thesis, Université de Montréal, 2012.
  2. Michael Blondin, Andreas Krebs et Pierre McKenzie. The Complexity of Intersecting Finite Automata Having Few Final States, Computational Complexity (CC), 2014.
  3. Michael Wehar. Hardness Results for Intersection Non-Emptiness. ICALP, 2014.
$\endgroup$
  • 2
    $\begingroup$ Thanks a lot! I accept your answer. The question originated from some practical tests where everything reduced after many steps into intersecting the solutions of many DFA with this particular characteristics. Nevertheless, we observed that although at the end we would obtain a simple DFA, the process never finished because of the intermediate DFAs (while sequentially intersecting) were wildly growing into an exponential number of states. Thus the question, of how to obtain the answer without going through the intermediary "naive" steps. $\endgroup$ – ale64bit Jan 6 '15 at 0:36
  • 1
    $\begingroup$ Thanks a lot (and sorry for being unclear, I'm below novice in this area). Now there's something I don't get. You mention that "shaped as tree" means "unique path from the root to every other node". But, for example, in the image you posted in the edit, that wouldn't be a tree (unless you count the 0/1 transitions as a single label)? $\endgroup$ – ale64bit Jan 6 '15 at 4:18
  • 1
    $\begingroup$ You are right, but my understanding was that you allow "don't care" transitions. Isn't it the case? $\endgroup$ – Michael Blondin Jan 6 '15 at 4:21
  • 2
    $\begingroup$ Hi Michael. Thanks for the nice answer. I hope all is well. :) $\endgroup$ – Michael Wehar Jan 6 '15 at 18:22
  • 2
    $\begingroup$ @MichaelWehar In case you fix both k and c, you mention you can solve the problem "quickly". But you don't mention the time complexity, only the space complexity. What exactly "quickly" means in that context? $\endgroup$ – ale64bit Jan 9 '15 at 16:07

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.