1
$\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$

2 Answers 2

4
$\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$
2
$\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$
7
  • $\begingroup$ what about regular expressions $\endgroup$ Oct 25 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
    Oct 25 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
    Oct 25 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
    Oct 25 at 12:59
  • $\begingroup$ @NealYoung, indeed, for NFA it follows. Regular expressions are left. $\endgroup$ Oct 25 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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