3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. :) $\endgroup$ Commented Jan 1, 2023 at 4:00

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ what about regular expressions $\endgroup$ Commented Oct 25, 2022 at 9:10
  • $\begingroup$ 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. $\endgroup$
    – MRC
    Commented Oct 25, 2022 at 9:19
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Oct 25, 2022 at 12:58
  • $\begingroup$ @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? $\endgroup$
    – Neal Young
    Commented Oct 25, 2022 at 12:59
  • 1
    $\begingroup$ Thanks so much for sharing this! I will write up an answer that covers both the constant and non-constant cases. $\endgroup$ Commented Jan 1, 2023 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.