Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
The intersection non-emptiness problem is defined as follows:
Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a non-empty intersection. In other, the goal is to determine if there exists a string that is accepted by all of the automata in the list.
This problem is PSPACE-complete.
Is the complexity known when we change DFA by regular expression or NFA?
As @MRC pointed stated, for NFAs the problem is also PSPACE-complete. However, I think the proof suggested by MRC does not cover the case you have in mind, when $k$ is non-constant, so I will give a complete proof here.
Lemma 1. With NFAs or regular expressions, the problem is PSPACE-complete.
Proof. First we give a proof for NFA variant. With DFAs the problem is known to be PSPACE-complete (shown originally by Kozen, I believe). The NFA variant cannot be easier (as the DFA variant is a restriction of the NFA variant), so the NFA variant is at least PSPACE-hard. It remains to verify that the NFA variant is in PSPACE.
It seems that the proof that the DFA variant is in PSPACE, as summarized here, adapts easily to the NFA variant. That proof uses Savitch's theorem, by which PSPACE = NPSPACE. So it suffices to describe a non-deterministic, polynomial-space verifier for the problem.
The input is a list of $n$ NFAs, each with at most $m$ states. The (non-deterministic, polynomial space) algorithm just non-deterministically guesses the string in the intersection, character by character, meanwhile simulating concurrently, in lockstep, each given NFA on the guessed string, character by character, keeping track of just one state per given NFA. If it ever reaches a step where all machines are in an accept state, it accepts. It requires only polynomial space, because at any point it only has to store $n$ states, one for each of the given NFAs.
This shows that the NFA variant is in PSPACE. The regular-expression variant reduces in polynomial time (and space) to the NFA variant, simply by converting each regular expression into an NFA by the standard polynomial-time algorithm. So the regular-expression variant is also in PSPACE. $~~~\Box$
By the way, the approach of explicitly constructing the NFA for the intersection of the given NFAs (using the standard Cartesian product construction) fails because that NFA can have as many as $m^n$ states, so in general has size exponentially large in the input size.
Short Answer
The NFA and DFA intersection problems have nearly equivalent time and space complexities.
Longer Answer
The NFA intersection problem can be efficiently reduced to the DFA intersection problem in a parameter preserving way. In particular, there exists an efficient reduction $r$ and a constant $c$ such that $r$ reduces any $k$ NFA's with $n$ states each to $k$ DFA's with $O(n^c)$ states each such that the NFA's have a non-empty intersection if and only if the DFA's have a non-empty intersection.
Remark: This reduction still works even if $k$ is non-constant. In other words, the NFA intersection problem is fpt-reducible to the DFA intersection problem where the parameter $k$ is preserved.
Justification
The following is basically Corollary 3.6 from my thesis on this topic.
Let me explain how this reduction works.
Part 1: The NFA intersection problem for $k$ NFA's with at most $n$ states each can be solved non-deterministically using at most $O(k \log(n))$ bits of memory with a multitape Turing machine.
Part 2: Any language accepted by a non-deterministic multitape Turing machine that uses at most $c \cdot k \cdot \log(n)$ bits of memory can be reduced to the DFA intersection problem in such a way that we obtain $k$ DFA's each with at most $O(n^{d \cdot c})$ states for some constant $d$ independent of $n$ and $k$.
We obtain the desired reduction by combining parts 1 and 2.
Conclusions
The DFA intersection problem is known to be PSPACE-complete (see Kozen 1977). When parameterized by the number of automata, it is also known to be XNL-complete. Because the NFA intersection problem is trivially at least as hard as the DFA intersection problem and the NFA intersection problem is solvable in $\mathrm{NSPACE}(k \log(n)) \subseteq \mathrm{DSPACE}(k^2 \log^{2}(n))$, it follows that the NFA intersection problem is PSPACE-complete (and XNL-complete when parameterized by the number of automata).
Furthermore, by the reduction above, if the DFA intersection problem is solvable in $\mathrm{TIME}(t(k, n))$ and $\mathrm{SPACE}(s(k, n))$ for some multivariate functions $t$ and $s$, then the NFA intersection problem is solvable in $\mathrm{TIME}(t(k, n^c))$ and $\mathrm{SPACE}(s(k, n^c))$ for some constant $c$ independent of $k$ and $n$. This confirms my initial claim that they have nearly equivalent time and space complexities.
Additional Readings
For more information on the automata intersection problems, please see the following list of publications.
When using NFAs, this problem is no harder than DFA intersection emptiness (space complexity wise). Computing the intersection of NFAs has the same space and time complexity as for DFAs (if you don't care about determinizing it), and so given $k$ NFAs with a max of $n$ states, the size of the resulting intersection NFA is at most $O(n^k)$ states. Then you only have to run reachability analysis (is there a path from the start state to any final state), which again can be done in polynomial space. Thus, NFA non-emptiness is in PSPACE.
There are apparently some open problems regarding the lower bound, so hopefully Michael Wehar shows up to elaborate.
Here are some other resources:
https://link.springer.com/chapter/10.1007/978-3-662-43951-7_30
Deciding emptiness of intersection of regular languages in subquadratic time
