State complexity of difference of two languages Given $A_1$ - DFA with $n$ states, $A_2$ - NFA with $m$ states (both over the same alphabet - $\Sigma$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal DFA, recognizing the language $L(A_1)\setminus L(A_2)=L(A_1) \cap(\Sigma^*\setminus L(A_2))$.
What I thought of: evaluate the state complexity of $\Sigma^*\setminus L(A_2)$ (hypothesis: $2^m$). Why? Because an upper bound of $2^m$ can be obtained for a DFA to accept the language of $A_2$. It's also known that the state complexity of the completion $\Sigma^*\setminus L(A_{min})$ is $k$, where $A_{min}$ is an arbitrary minimal $DFA$ with $k$ states. Therefore we can evaluate the upper bound of the minimal DFA, recognizing $L(A_1) \cap(\Sigma^*\setminus L(A_2))$ as $n2^m$ (the state complexity of the intersection is simply the product of states).
This is correct, and moreover it is tight for $n = 1$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $m$-state NFAs which require $2^m$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $A_1 = \Sigma^*$ we obtain a tight example with $n = 1$ and any $m$.
It is an interesting question whether the bound is tight for all $n$. This is likely the case if we take for $L(A_1)$ the language $(\Sigma^n)^*$.