DFA intersection algorithm for special cases

Question

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:

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.

Answer 1

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$

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.