<p>This is coNP-hard even if <span class="math-container">$B$</span> is also acyclic.</p>

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

<p>To do this, you build an automaton <span class="math-container">$B_i$</span> with <span class="math-container">$n+2$</span> states recognizing <span class="math-container">$T_i$</span> and add an initial state that non-deterministically chooses <span class="math-container">$i$</span> and jumps into <span class="math-container">$B_i$</span> with an <span class="math-container">$\epsilon$</span>-transition. </p>

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

<p>Now you build <span class="math-container">$A$</span>, acyclic, which accepts every word of length <span class="math-container">$n$</span> (same construction as before for <span class="math-container">$T_i$</span> empty).</p>

<p>It is clear that <span class="math-container">$L(A) \subseteq L(B)$</span> iff <span class="math-container">$D$</span> is a tautology, which is 
coNP-complete.</p>

CC BY-SA 4.0
2020-02-02T08:10:38.230Z
2020-02-02T08:10:38.230Z
holf
<p>Let <span class="math-container">$A$</span> and <span class="math-container">$B$</span> be NFAs, such that <span class="math-container">$A$</span> is acyclic.</p>

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

<p>Can it be shown that it is <span class="math-container">$coNP$</span>-hard?</p>

<complexity-classes><automata-theory><nfa>
Containment problem of an acyclic NFA in an NFA
RaLo18
# Containment problem of an acyclic NFA in an NFA

(Asked by: username_0 on 2020-02-01)

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?

**Tags:** complexity-classes, automata-theory, nfa


---

## 1 answers

### Answer by username_1 on 2020-02-02. Score: 8 | Accepted 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.


---

