Minimal state DFAs for a regular expression of length $n$

Question

I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering though if there are any known bounds on the number of states in the DFA even without going through with a construction.

Specifically, let $R$ be a regular expressions having length $n$ (by length here I mean the length of the whole string $R$ including alphabet symbols, parentheses, etc.). Is there a known general sub-exponential upper-bound function $f(n)$ such that for any such $R$, the minimal state DFA accepting $L(R)$ always has $\leq f(n)$ states? Or can it be proven that there are always counterexamples?

Answer 1

According to Theorem 11 of Gruber and Holzer, From Finite Automata to Regular Expressions and Back – A Summary on Descriptional Complexity, $f(n) = 2^{\Theta(n)}$ (essentially; the lower bound is only for infinitely many $n$). While the theorem is stated for alphabetic width, according to Theorem 2 in the same paper, this measure is within constant factors of the length.