Slowest growing upper bound for the minimum length of a complementary prefix regular expression

Question

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?

Answer 1

Wikipedia says that taking the complement "can cause a double exponentially blow-up of its length" and cites the following paper:

Succinctness of the Complement and Intersection of Regular Expressions. Wouter Gelade and Frank Neven. STAC 2008.

In particular, they give a concrete language that triggers the doubly exponential blowup. See Theorem 4.1 in the paper.

That paper considers the normal representation for regexps rather than postfix, but I don't see any reason to expect that to change the bottom line. You could work through their example and their proof if you want to be sure.