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.