<p><strong>Short Answer</strong></p>
<p>The NFA and DFA intersection problems have nearly equivalent time and space complexities.</p>
<p><strong>Longer Answer</strong></p>
<p>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 <span class="math-container">$r$</span> and a constant <span class="math-container">$c$</span> such that <span class="math-container">$r$</span> reduces any <span class="math-container">$k$</span> NFA's with <span class="math-container">$n$</span> states each to <span class="math-container">$k$</span> DFA's with <span class="math-container">$O(n^c)$</span> states each such that the NFA's have a non-empty intersection if and only if the DFA's have a non-empty intersection.</p>
<p><em>Remark: This reduction still works even if <span class="math-container">$k$</span> is non-constant. In other words, the NFA intersection problem is fpt-reducible to the DFA intersection problem where the parameter <span class="math-container">$k$</span> is preserved.</em></p>
<p><strong>Justification</strong></p>
<p>The following is basically Corollary 3.6 from <a href="http://michaelwehar.com/documents/mwehar_dissertation.pdf" rel="nofollow noreferrer">my thesis</a> on this topic.</p>
<p>Let me explain how this reduction works.</p>
<p><em>Part 1: The NFA intersection problem for <span class="math-container">$k$</span> NFA's with at most <span class="math-container">$n$</span> states each can be solved non-deterministically using at most <span class="math-container">$O(k \log(n))$</span> bits of memory with a multitape Turing machine.</em></p>
<p><em>Part 2: Any language accepted by a non-deterministic multitape Turing machine that uses at most <span class="math-container">$c \cdot k \cdot \log(n)$</span> bits of memory can be reduced to the DFA intersection problem in such a way that we obtain <span class="math-container">$k$</span> DFA's each with at most <span class="math-container">$O(n^{d \cdot c})$</span> states for some constant <span class="math-container">$d$</span> independent of <span class="math-container">$n$</span> and <span class="math-container">$k$</span>.</em></p>
<p>We obtain the desired reduction by combining parts 1 and 2.</p>
<p><strong>Conclusions</strong></p>
<p>The DFA intersection problem is known to be PSPACE-complete (see <a href="https://www.cs.cornell.edu/%7Ekozen/Papers/LowerBounds.pdf" rel="nofollow noreferrer">Kozen 1977</a>).  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 <span class="math-container">$\mathrm{NSPACE}(k \log(n)) \subseteq \mathrm{DSPACE}(k^2 \log^{2}(n))$</span>, it follows that the NFA intersection problem is PSPACE-complete (and XNL-complete when parameterized by the number of automata).</p>
<p>Furthermore, by the reduction above, if the DFA intersection problem is solvable in <span class="math-container">$\mathrm{TIME}(t(k, n))$</span> and <span class="math-container">$\mathrm{SPACE}(s(k, n))$</span> for some multivariate functions <span class="math-container">$t$</span> and <span class="math-container">$s$</span>, then the NFA intersection problem is solvable in <span class="math-container">$\mathrm{TIME}(t(k, n^c))$</span> and <span class="math-container">$\mathrm{SPACE}(s(k, n^c))$</span> for some constant <span class="math-container">$c$</span> independent of <span class="math-container">$k$</span> and <span class="math-container">$n$</span>.  This confirms my initial claim that they have nearly equivalent time and space complexities.</p>
<p><strong>Additional Readings</strong></p>
<p>For more information on the automata intersection problems, please see the following <a href="https://en.wikipedia.org/wiki/Talk:Intersection_non-emptiness_problem#Relevant_Publications" rel="nofollow noreferrer">list of publications</a>.</p>

CC BY-SA 4.0
2023-01-01T03:58:38.997Z
2023-01-01T14:02:22.067Z
2023-01-01T14:02:22.067Z
Michael Wehar
<p>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 <span class="math-container">$k$</span> NFAs with a max of <span class="math-container">$n$</span> states, the size of the resulting intersection NFA is at most <span class="math-container">$O(n^k)$</span> states. Then you only have to run reachability analysis (is there a path from the start state to <em>any</em> final state), which again can be done in polynomial space. Thus, NFA non-emptiness is in PSPACE.</p>
<p>There are apparently some open problems regarding the lower bound, so hopefully <a href="https://cstheory.stackexchange.com/users/14207/michael-wehar">Michael Wehar</a> shows up to elaborate.</p>
<p>Here are some other resources:</p>
<p><a href="https://link.springer.com/chapter/10.1007/978-3-662-43951-7_30" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007/978-3-662-43951-7_30</a></p>
<p><a href="https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time">Deciding emptiness of intersection of regular languages in subquadratic time</a></p>

CC BY-SA 4.0
2022-10-25T09:10:47.223Z
what about regular expressions
user1868607
CC BY-SA 4.0
2022-10-25T09:19:42.843Z
It would be exactly the same, as given a regex with length $m$, you can build an $O(m)$ state NFA in $O(m)$ time that recognizes the same language. So you just convert all regex to NFA and then do the intersection-emptiness, and there is no time increase from the NFA case.
MRC
CC BY-SA 4.0
2022-10-25T12:58:38.037Z
Does this answer assume that the number of NFAs given ($k$ in the answer) is $O(1)$?  Because otherwise what you describe (taking space $n^k$) isn't polynomial in the input size.  Am I missing something?  The question in the post doesn't seem to assume $k$ is constant.
Neal Young
CC BY-SA 4.0
2022-10-25T12:59:29.990Z
@user1868607, When you allow NFA instead of just DFA it doesn't get easier (as any DFA is also an NFA).  So it should still be PSPACE-hard, right?
Neal Young
CC BY-SA 4.0
2022-10-25T13:04:21.607Z
@NealYoung, indeed, for NFA it follows. Regular expressions are left.
user1868607
CC BY-SA 4.0
2022-10-26T00:38:39.387Z
@user1868607, doesn't essentially the same argument show that regular expressions are hard as well?  (Given an instance with DFAs, you can convert it into a poly-size instance with regular expressions, right?)  But I'm not sure that the answer given in this answer covers the case when $k$ is not constant, which I believe is the case that you have in mind, right?
Neal Young
CC BY-SA 4.0
2022-10-26T15:09:43.903Z
@NealYoung indeed $k$ is non-constant in my setting
user1868607
CC BY-SA 4.0
2023-01-01T03:59:35.943Z
Thanks so much for sharing this!  I will write up an answer that covers both the constant and non-constant cases.
Michael Wehar
CC BY-SA 4.0
2022-10-25T05:04:17.380Z
2022-10-25T09:28:56.100Z
2022-10-25T09:28:56.100Z
MRC
<p>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 <span class="math-container">$k$</span> is non-constant, so I will give a complete proof here.</p>
<p><strong>Lemma 1.</strong> <em>With NFAs or regular expressions, the problem is PSPACE-complete.</em></p>
<p><em>Proof.</em> 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.</p>
<p>It seems that the proof that the DFA variant is in PSPACE, as summarized <a href="https://cs.stackexchange.com/questions/119317/pspace-completeness-of-dfa-intersection-problem">here</a>, 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.</p>
<p>The input is a list of <span class="math-container">$n$</span> NFAs, each with at most <span class="math-container">$m$</span> 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 <span class="math-container">$n$</span> states, one for each of the given NFAs.</p>
<p>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.  <span class="math-container">$~~~\Box$</span></p>
<p>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 <span class="math-container">$m^n$</span> states, so in general has size exponentially large in the input size.</p>

CC BY-SA 4.0
2022-10-31T01:47:56.237Z
2022-10-31T01:47:56.237Z
Neal Young
<p>The intersection non-emptiness problem is defined as follows:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>This problem is PSPACE-complete.</p>
<p>Is the complexity known when we change DFA by regular expression or NFA?</p>

CC BY-SA 4.0
2023-01-01T04:00:37.640Z
Thanks so much for asking about this! I worked on the DFA intersection problem for my PhD thesis.  There seems to be some good answers below, but feel free to reach out to me if you would like to discuss further as I find this topic fascinating. :)
Michael Wehar
<cc.complexity-theory><automata-theory>
Intersection non-emptiness problem over regular expressions and NFA
user1868607
# Intersection non-emptiness problem over regular expressions and NFA

(Asked by: username_0 on 2022-10-24)

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?

**Tags:** cc.complexity-theory, automata-theory

> **Comments:**
> **username_1**: Thanks so much for asking about this! I worked on the DFA intersection problem for my PhD thesis.  There seems to be some good answers below, but feel free to reach out to me if you would like to discuss further as I find this topic fascinating. :)  

---

## 3 answers

### Answer by username_3 on 2022-10-31. Score: 7 | Accepted answer

As @username_2 pointed stated, for NFAs the problem is also PSPACE-complete. However, I think the proof suggested by username_2 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](https://cs.stackexchange.com/questions/119317/pspace-completeness-of-dfa-intersection-problem), 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.


---

### Answer by username_1 on 2023-01-01. Score: 5

**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](http://michaelwehar.com/documents/mwehar_dissertation.pdf) 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](https://www.cs.cornell.edu/%7Ekozen/Papers/LowerBounds.pdf)). 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](https://en.wikipedia.org/wiki/Talk:Intersection_non-emptiness_problem#Relevant_Publications).


---

### Answer by username_2 on 2022-10-25. Score: 3

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 [username_1](https://cstheory.stackexchange.com/users/14207/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](https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time)

> **Comments:**
> **username_0**: what about regular expressions  
> **username_2**: It would be exactly the same, as given a regex with length $m$, you can build an $O(m)$ state NFA in $O(m)$ time that recognizes the same language. So you just convert all regex to NFA and then do the intersection-emptiness, and there is no time increase from the NFA case.  
> **username_3**: Does this answer assume that the number of NFAs given ($k$ in the answer) is $O(1)$?  Because otherwise what you describe (taking space $n^k$) isn't polynomial in the input size.  Am I missing something?  The question in the post doesn't seem to assume $k$ is constant.  
> **username_3**: @username_0, When you allow NFA instead of just DFA it doesn't get easier (as any DFA is also an NFA).  So it should still be PSPACE-hard, right?  
> **username_0**: @NealYoung, indeed, for NFA it follows. Regular expressions are left.  
> **username_3**: @username_0, doesn't essentially the same argument show that regular expressions are hard as well?  (Given an instance with DFAs, you can convert it into a poly-size instance with regular expressions, right?)  But I'm not sure that the answer given in this answer covers the case when $k$ is not constant, which I believe is the case that you have in mind, right?  
> **username_0**: @NealYoung indeed $k$ is non-constant in my setting  
> **username_1**: Thanks so much for sharing this!  I will write up an answer that covers both the constant and non-constant cases.  

---

