A postfix regular expression acting on a binary alphabet (specification from this post) can be described using the following grammar,
R → 0 or 1 or _ or ! or RR; or RR| or R+
where,
0
and 1
match their selves,
!
matches nothing,
_
matches the empty string,
;
is concatenation,
|
is alternation,
R+
matches 1 or more occurrences of R
.
(The linked post above gives some example regular expressions and the strings it matches.)
What is the slowest growing upper bound on the length of the regular expression complementary to another regular expression as a function of the length of the latter?
So far, I have a double exponential. I show that an "input" regular expression $r_1$ will give an NFA that has 1 more state than the length of $r_1$. By the powerset construction, the resulting DFA will a maximum of have $2^{1+\text{length(}r_1\text{)}}$ states. Clearly, the complementary DFA will have the same number of states, i.e. the same size.
I then use an algorithm to construct a regular expression given a DFA to get the upper bound of the length of this regular expression as a function of the size of the DFA. This gave another exponential, $\frac{16}{3}(4^n-1)$ where $n$ is the size of the DFA.
Combining the two gives $\frac{16}{3}(4^{2^{n+1}}-1)$, where $n$ is the length of $r_1$, as the length of the complementary regular expression. I am not concerned about the constants, as stated in the question, only how fast it grows. So, if I got my big-O notation correct, this gives $O\left(4^{2^n}\right)$.
This seems unnecessarily large, can it be lower? Can it be lowered to a mere exponential?