Let $\Sigma$ be an alphabet of size $2$, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ minimal DFAs $D_i$ whose size are bounded by $m$. As the number $k$ of minimal DFAs of size at most $m$ is finite, there exists a function $f$ that returns this number $k=f(m)$.
Let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$.
Is the size of the smallest DFA $D_L$ recognizing $L$ always below $m^{f(m)}$ ?
And if so, how can we find a precise definition/close-form of $f(m)$ ?
My intuition is as follows : the size of a DFA resulting from the union of two DFAs $A$ and $B$ is not greater than $|A|.|B|$. Thus, if there are not more than $f(m)$ minimal DFAs of size at most $m$ then the size of the minimal DFA for the union of the $D_i$ can not exceed $m^{f(m)}$. Sounds correct ?
Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs. In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}.m.2^m = 2^m.m^{2m+1}$.
Thus we can conclude that for $|\Sigma|=2$ the maximal number of states required for the union of $n$ DFAs of size at most $m$ is bounded by $m^{f(m)} = m^{2^m.m^{2m+1}}$.
We can then generalize to an arbitrary alphabet $\Sigma$ : the bound becomes $f(m) \le 2^m.m^{|\Sigma|m+1}$. But it looks like this bound could be tighter though...
Does someone have a better estimate ?
One motivation to find a tighter bound is that if we fix the amount $S$ (in number of states) of memory that is available on a computer then we could easily get the maximal size $m$ that the $n$ DFAs must not exceed in order to guarantee the complete computation of the minimal DFA $D_L$ for the union of the $n$ DFAs.
I would appreciate if possible, some papers related to this problem or a proof/counter-example.
Many thanks, Luz