9
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

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.