Optimal upper bound on the number of states in the complement of an NFA

Question

I have my own version of lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version also supports the generation of NFAs (Non-deterministic Finite Automaton) and of course I try to keep the automatons as small as possible.

My question thus is: what is the most optimal known upper bound on the number of states in the NFA that accepts the complement of another NFA? Of course going through the conversion to a DFA (Deterministic Finite Automaton) and then interchanging accepting and rejecting states, gives an exponential upper bound. Are there any better known upper bounds? Preferably polynomial or even linear of course.

If no better upper bound is known, has it been shown that for some family of languages the lower bound is exponential or otherwise super polynomial?

Answer 1

In the paper State Complexity of Concatenation and Complementation of Regular Languages by Jirásek, Jirásková
, and Szabari (LNCS Volume 3317, 2005, doi 10.1007/978-3-540-30500-2_17) very precise bounds for complexities for complement on non-deterministic automata are obtained. We do not need full details, but the authors cite an earlier report by one of them, stating:

Theorem 2. For any positive integer $n$, there exists a binary NFA $M$ of $n$ states such that any NFA for the complement of the language $L(M)$ needs at least $2^n$ states.

So it seems there is no better bound for complementation than via deterministic automata. At least in general.