10
$\begingroup$

What is the complexity, given as input an NFA, of determining if it is cofinite (i.e., the complement of its language is finite)?

Surely this must be known but I can't find a reference. Note that the problem of determining if an NFA is universal is PSPACE-complete, but I don't see an obvious reduction.

$\endgroup$
2
  • 3
    $\begingroup$ Determining if the language is finite is a simple reachability problem, thus computable in NL, and consequently cofiniteness is computable in PSPACE by applying this to the complement. So I suppose the problem is whether it is PSPACE-hard, right? $\endgroup$ Mar 22 at 20:18
  • $\begingroup$ Yes, thanks for your answer! (I accepted Neal's answer as this is the less "obvious" direction, but I would have accepted both if I could) $\endgroup$
    – M.Monet
    Mar 25 at 7:42

2 Answers 2

14
$\begingroup$

Lemma 1. Determining whether a given NFA is cofinite is PSPACE-hard.

Proof. The proof is by an easy reduction from the PSPACE-complete problem of determining whether a given NFA is universal. The reduction is similar to one here. Given an NFA $N$, the reduction outputs (in poly-time) the NFA $N'$ whose language is $$L(N') = (L(N) \cdot \#)^* \cdot L(N),$$ where $\#$ is a new letter added to the alphabet of $N$.

Given $N$ such an NFA $N'$ can be constructed in poly time.

Now suppose that $N$ is universal. Letting $\Sigma$ be the alphabet of $N$, any string $x$ over the alphabet $\Sigma' = \Sigma\cup\{\#\}$ of $N'$ is of the form $$x = w_1 \# w_2 \# \cdots \# w_k$$ where $w_i\in \Sigma^*$. Such a string $x$ is in $L(N')$ iff each $w_i$ is in $L(N)$. So, if $N$ is universal, then every such string $x$ is in $L(N')$, so $L(N')$ is universal and cofinite.

On the other hand, if $N$ is not universal, then some string $w$ is not in $L(N)$, so every $x$ (as described above) with any $w_i = w$ is not in $L(N')$. There are infinitely many such $x$, so the complement of $L(N')$ is infinite. That is, $N'$ is not cofinite.

So $N'$ is cofinite iff $N$ is universal, the reduction is correct, and determining whether $N'$ is cofinite is PSPACE-hard. $~~~\Box$

As Emil details in another answer, the problem is in PSPACE, by a proof similar to the one that shows universality is in PSPACE. So the problem is PSPACE-complete.

$\endgroup$
1
  • $\begingroup$ Ah, that's a nice argument, thanks! :) $\endgroup$
    – a3nm
    Mar 23 at 8:27
8
$\begingroup$

Since the other answer makes it sound as if it were not obvious, let me point out that the problem is computable in PSPACE. First, we observe:

Lemma. For any NFA $A$ with $n$ states, the following are equivalent:

  1. $L(A)$ is infinite.
  2. $A$ accepts a word of length $\ge n$.
  3. There is an accepting run of $A$ that goes through some state twice.

Either condition 2 or 3 can be checked in NL.

Proof: 1 → 2 is obvious. 2 → 3: An accepting run of length $\ge n$ (hence with $\ge n+1$ states, including the starting and final states) must repeat some state by the pigeonhole principle. 3 → 1: We can repeat the part of the accepting run between two occurrences of the same state as many times as we want, yielding arbitrary long accepted words.

Corollary. Cofiniteness for NFA can be checked in $\mathrm{coNPSPACE=PSPACE}$.

Proof: Determinize the automaton using the powerset construction, flip accepting and rejecting states, and apply the Lemma to the result. It is not necessary to construct the whole powerset automaton in advance—we can just guess transitions on the fly, storing only a representation of the current state (i.e., a subset of the original automaton), hence the needed space is only $O(n)$ (for a nondeterministic algorithm).

$\endgroup$
1
  • $\begingroup$ Thanks for clarifying this! $\endgroup$
    – a3nm
    Mar 23 at 8:27

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.