The problem of the enumeration of minimal (non-isomorphic) n state acyclic deterministic finite automata (MADFAs) is an open problem that recently has been considered by several authors. Domaratzki presented a characterization of MADFAs, gave a lower bound and an upper bound for these values. The lower bound was based upon the enumeration of certain families of MADFAs, and the upper bound was obtained by enumerating initially-connected acyclic deterministic finite automata (ICADFAs), where states have associated a topological order. This approach has the drawback of considering labelled automata, and thus possible isomorphic ones. Câmpeanu and Ho gave a tight upper bound for the number of states of a MADFAs accepting words of length less than or equal to a given integer. Liskovets gave a linear recursive relation for the number of unlabelled (non-isomorphic) ICADFAs, and has also enumerated ICADFAs with a unique pre-dead state. As all MADFAs have this characteristic, a better upper bound is thus achieved.

In this talk we give a canonical representation for MADFAS with n states over an alphabet of k symbols. Using this normal form, we present a method for the exact generation of MADFAs. This method has the advantage of avoiding a rejection phase that would be needed if a generation algorithm for a larger class of automata that contains the MADFAs were considered. It is also relevant to note that although Liskovets obtained an exact formula for the enumeration of unlabelled initially-connected acyclic deterministic finite automata, no normal form or exact generator algorithm is known for that class. We also give an upper bound for MADFAs enumeration that is exact for small values of n.