# Containment problem of an acyclic NFA in an NFA

Let $$A$$ and $$B$$ be NFAs, such that $$A$$ is acyclic.

In the general case, deciding whether $$L(A)\subseteq L(B)$$ is $$PSPACE$$-hard. However, since $$A$$ is acyclic, we know that for every $$w \in L(A)$$, it holds that $$|w|$$ is linear in $$|A|$$. It follows that if $$L(A) \nsubseteq L(B)$$, there must be a polynomial witness $$w\in L(A)\setminus L(B)$$. Thus, the containment problem when $$A$$ is acyclic is in $$coNP$$.

Can it be shown that it is $$coNP$$-hard?

## 1 Answer

This is coNP-hard even if $$B$$ is also acyclic.

Let $$D = \bigvee_{i=1}^m T_i$$ be a DNF on variables $$x_1, \dots, x_n$$. We can easily contruct an NFA $$B$$ accepting exactly the satisfying assignment of $$D$$, that is, the words $$w \in \{0,1\}^n$$ such that the assignment $$a$$ defined as $$a(x_i) = w_i$$ satisfies $$D$$.

To do this, you build an automaton $$B_i$$ with $$n+2$$ states recognizing $$T_i$$ and add an initial state that non-deterministically chooses $$i$$ and jumps into $$B_i$$ with an $$\epsilon$$-transition.

$$B_i$$ has states $$q_1, \dots, q_{n+1}$$, and $$reject$$. Initial state is $$q_1$$. When in state $$q_j$$ for $$j \leq n$$: if $$x_j$$ does not appear in $$T_i$$, then you go in state $$q_{j+1}$$ for every value of the next letter. If $$x_j$$ appears positively in $$T_i$$, then you go in $$q_{j+1}$$ only if you read letter $$1$$. If you read letter $$0$$, you go in state $$reject$$. If $$x_j$$ appears negatively in $$T_i$$, you do the same by swapping $$0$$ and $$1$$. $$q_{n+1}$$ is the only final state.

Now you build $$A$$, acyclic, which accepts every word of length $$n$$ (same construction as before for $$T_i$$ empty).

It is clear that $$L(A) \subseteq L(B)$$ iff $$D$$ is a tautology, which is coNP-complete.