Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
