Minimal acyclic deterministic finite automata (MADFAs) are frequently used to represent dictionaries, i.e. finite sets of finite words, in e.g. spell checkers, network security, packet filtering applications, and other tools. Given the size of such dictionaries, which may run into millions of words, their efficient construction is a critical issue. Acyclic Deterministic Finite Automata (ADFAs) consist of a set of states, one of them being a start state, and one or more of them being final states; and labeled transitions between states. They are deterministic, i.e. each state has at most one out-transition for a specific label; and they are acyclic, i.e. as their name says, no cycles occur. An ADFA is a MADFA if no other ADFA with fewer states accepts the same set of words. This makes MADFAs an excellent data structure to store large finite word sets like dictionaries. As a result, quite some research has gone into MADFA construction algorithms, and a number of different ones, with different characteristics, have been developed [1]. Yet no coherent implementation covering all these algorithm variants existed. In this talk, we report on our experience implementing these algorithms in a coherent Java-based toolkit, and on initial empirical performance results obtained.

[1] B. W. Watson. Constructing Minimal Acyclic Deterministic Finite Automata. PhD thesis, University of Pretoria, 2010.