Number of minimal DFAs of size at most $m$?

Question

Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$. Let $f(m)$ denote the number of different such minimal DFAs.

Can we find a closed-form formula for $f(m)$?

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 (as suggested in the comments). 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}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$.

We can generalize to an arbitrary alphabet $\Sigma$: the bound becomes $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$.

But we bounded here arbitrary DFAs and I'm interested in bounding the number of minimal DFAs. Thus, it looks like this bound could be tighter... Does someone have a better estimate?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

Answer 1

According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with $n$ states, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , the VC-dimension of the concept class of $n$-state DFAs over an alphabet of size $k$ is $$ d=d(n,k) := (k-1+o(1))n\log_2 n.$$ It follows that there are at least $2^d$ distinct $n$-state automata on a $k$-letter alphabet. The upper bound on the number such automata follows from a simple counting argument (given in the paper), and is at most $2^d$.

Answer 2

(NB: the upper bound given in the accepted answer is better or equal to the one given here)

An upper bound is proposed in this paper given in one of the previous comments: “On the number of distinct languages accepted by finite automata with n states” (2002, M. Domaratzki, D. Kisman, J. Shallit).

In this paper:

• the $f_{|\Sigma|}(m)$ function provides the number of distinct non-isomorphic minimal DFAs with $m$-states over a ${|\Sigma|}$-letter alphabet,
• the $g_{|\Sigma|}(m)$ function gives the number of distinct languages accepted by DFAs with $m$ states over a ${|\Sigma|}$-letter alphabet.

We are interested in the upper bound for the $g_{|\Sigma|}(m)$ function, since my question ask for an upper bound on the number of minimal DFAs with at most $m$ states (and not exactly $m$).

What I understand from the page $6$ below Theorem $8$ is that $g_{|\Sigma|}(m) \leq \frac{2^m\cdot m^{|\Sigma|m}}{(m-1)!}$ which is a better bound than the one given in my question (i.e. $2^m\cdot m^{|\Sigma|m+1}$). This partially answers my question.

But the paper claims that this upper bound is trivial and can be improved. However, the improvement only deals with $f_{|\Sigma|}(m)$ (as far as I understand it).